pku 1122

2009年7月29日

题目链接：PKU 1122 FDNY to the Rescue!
  
分类：Diskastra

题目分析与算法原型
        有点郁闷，这题由于题目意思没看仔细加上有些位置没有理解充分，贡献了好几次WA，虽然只是一个Dijkastra的简单应用，不过此题还是要细心应对的，大致做法是先将输入的矩阵转置一下，使得单终点最短路径变成单源点最短路径，然后用Dijkastra处理即可（注意题目的一些提示条件，看清楚题目意思）


Code:

  1#include<stdio.h>
  2#include<stdlib.h>
  3#include<string.h>
  4#define max 1000000000
  5#define len 25
  6
  7int n,map[len][len],dis[len],s,adj[len],path[len],visit[len];
  8bool finish;
  9
 10struct node
 11{
 12    int dis,num;
 13}place[len];
 14
 15void init()
 16{
 17    int i,j;
 18    for(i=1;i<=n;i++)
 19        for(j=1;j<=n;j++)
 20        {
 21            if(i==j)map[i][j]=0;
 22            else map[i][j]=max;
 23        }
 24}
 25int cmp(const void * a,const void * b)
 26{
 27    return (*(node *)a).dis > (*(node *)b).dis ? 1:-1;
 28}
 29void Dijkastra(int s)//s为源点
 30{
 31    int i,j;
 32    for(i=1;i<=n;i++)
 33    {
 34        dis[i]=map[s][i];
 35        visit[i]=0;
 36        if(i!=s&&dis[i]<max)path[i]=s;
 37        else path[i]=-1;
 38    }
 39    visit[s]=1;
 40    for(i=1;i<n;i++)
 41    {
 42        int min=max,u;
 43        for(j=1;j<=n;j++)
 44            if(visit[j]==0&&dis[j]<min)
 45            {
 46                u=j;
 47                min=dis[j];
 48            }
 49            if(min==max)return;//此语句对于非连通图是必须的，表示当前已经不存在路径了
 50            visit[u]=1;
 51            for(j=1;j<=n;j++)
 52                if(visit[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
 53                {
 54                    dis[j]=dis[u]+map[u][j];
 55                    path[j]=u;
 56                }
 57    }
 58}
 59int main()
 60{
 61    int i,j,pos;
 62    while(scanf("%d",&n)!=EOF)
 63    {
 64        init();
 65        finish=false;
 66        for(i=1;i<=n;i++)
 67            for(j=1;j<=n;j++)
 68            {
 69                int l;
 70                scanf("%d",&l);
 71                if(l!=-1)map[j][i]=l;
 72            }
 73            scanf("%d",&s);
 74            pos=0;
 75            char ch;
 76            memset(adj,0,sizeof(adj));
 77
 78            printf("Org\tDest\tTime\tPath\n");
 79            while(1)
 80            {
 81                ch=getchar();
 82                if(ch==10)break;
 83                while(!(ch>='0'&&ch<='9'))ch=getchar();
 84                
 85                while(ch>='0'&&ch<='9')
 86                {
 87                    adj[pos]*=10;
 88                    adj[pos]+=ch-'0';
 89                    ch=getchar();
 90                }
 91                
 92                if(adj[pos]==s)
 93                {
 94                    printf("%d\t%d\t%d\t%d\n",s,s,0,s);
 95                    adj[pos]=0;
 96                }
 97                else pos++;
 98                if(ch==10)break;
 99            }
100            Dijkastra(s);
101            for(i=0;i<pos;i++)
102            {
103                place[i].dis=dis[adj[i]];
104                place[i].num=adj[i];
105            }
106            qsort(place,pos,sizeof(place[0]),cmp);
107            
108            
109            for(i=0;i<pos;i++)
110            {
111                printf("%d\t%d\t%d\t%d\t",place[i].num,s,place[i].dis,place[i].num);
112                int kk=path[place[i].num];
113                while(1)
114                {
115                    printf("%d",kk);
116                    if(kk==s)break;
117                    else printf("\t");
118                    kk=path[kk];
119                }
120                printf("\n");
121            }
122    }
123    return 0;            
124}

posted on 2009-07-29 20:12 蜗牛也Coding 阅读(241) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜