POJ 3767 I Wanna Go Home （dijkstra算法）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题目分析：

由于战争，一个商人想从城市1，回到自己的家城市2，其中城市1始终是由领导1，城市2始终由领导2，其中，商人回家的路中只能有一条路上连接由两个领导领导的城市，还有就是给出的路上双向的，也就是如果城市1能到城市2，那么城市2也同样能到城市1，这是关键。

由于这个题中从1类城市走到2类城市后就不能再回去，只能穿过一次，所以先存为双向路，后面再根据不同类型的城市，把双向路变为单向路

N个城市，城市编号为1,2,3，……N

M条路,路为双向路。提供每条路的长度及端点城市编号,每两个城市之间直接连通的路最多一条。

这N个城市分为两个集合，部分属于集合1，部分属于集合2，提供每个城市所属的集合，现要求从城市1出发去城市2，要求途径的路中最多出现一条其两端城市不属于同一个集合的路，求出符合该条件下的从城市1到城市2的最短路，若不存在符合条件的路，输出-1

注：数据中城市1必定属于集合1，城市2必定属于集合2

分析：由于城市1与城市2所属的集合固定，故在路径中必定有一条而且只能有一条路从属于集合 1的城市出发进入城市2，而定不会出现从集合2走向集合1的城市。

如此，M条路中凡是连接属于不同集合的城市的路为单向路，只能从集合1中的城市走向集合2, 在此基础上用Dijkstra算法求最短路即可。

核心算法 Dijkstra

思路：Dijkstra

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 #define inf 0xfffffff  //定义inf为无穷大 
 6 #define size 610
 7 int value[size][size];  //为true，则size为v0到size当前求得最短路径上的顶点 
 8 int d[size];  
 9 int lead[size];
10 bool visit[size];//为true，当且仅当size属于s，即已经求得最短路径上的顶点 
11 int n,m;
12 void djk()
13 {
14     int x,y,z,tab,temp;
15     memset(visit,0,sizeof(visit));  //设初值 
16     for(x=1;x<=n;x++)
17        d[x]=value[1][x]; //d[]存放1即(v0)到x即(v)的最短距离，初值为1到x的直接距离 
18     d[1]=0;  //1到1的距离为0 
19     visit[1]=1;  //1顶点并入s集 
20     for(x=1;x<n;x++)  //对于其余的n-1个顶点
21     {   //开始主循环，每次求得1即(v0)到某个顶点v的最短路径，并将v并入s集
22        temp=inf;  //当前所距离v0顶点的最近距离，设初值为∞ 
23        for(y=1;y<=n;y++)  //对所有顶点检查
24        {
25             if(!visit[y]&&d[y]<temp)  //在s集之外的顶点中
26             {   //找离1即v0最近的顶点y，并将其赋值给tab，距离赋给temp
27                  temp=d[y];
28                  tab=y;
29             }
30        }
31        visit[tab]=true;  //将tab并入s集
32        for(z=1;z<=n;z++)   //根据新并入的顶点，更新不在s集的顶点到v0的距离和路径数组
33        {
34             if(!visit[z]&&d[z]>d[tab]+value[tab][z]) //z不属于s集且v0到v到z的距离<目前v0到z的距离
35                d[z]=d[tab]+value[tab][z];  //更新d[z]
36        }
37     }
38     if(d[2]==inf)
39       cout<<"-1\n";  //若不存在符合条件的路，输出-1
40     else
41     cout<<d[2]<<endl;
42 }
43 int main()
44 {
45     while(cin>>n)
46     {
47         if(n==0)
48            break;
49         int i,j,a,b,len;
50         cin>>m;
51         memset(lead,0,sizeof(lead));
52         for(i=1;i<=n;i++)
53             for(j=1;j<=n;j++)
54                value[i][j]=inf;
55         for(i=1;i<=m;i++)
56         {
57             cin>>a>>b>>len;
58             value[a][b]=value[b][a]=len;
59         }
60         for(i=1;i<=n;i++)
61            cin>>lead[i];
62         for(i=1;i<=n;i++)
63         {
64             for(j=1;j<=n;j++)
65             {
66                 if(lead[i]!=lead[j])
67                 {
68                    if(lead[i]==1&&lead[j]==2)
69                       value[j][i]=inf;
70                    else     if(lead[i]==2&&lead[j]==1)
71                       value[i][j]=inf;
72                 }
73             }
74         }
75         djk();
76     }
77     return 0;
78 }
79

代码2：

 1 #include<stdio.h>
 2  #include<string.h>
 3  #include<stdlib.h>
 4  #define Max 0xfffffff
 5  int m[610][610],p[610];
 6  bool vis[610];
 7  bool leader[610];
 8  int vexnum,arcnum;
 9  void dijkstra()
10  {
11      int i,j,k,t,min;
12      memset(vis,0,sizeof(vis));
13      for(i=1;i<=vexnum;++i)
14          p[i]=m[1][i];
15      for(vis[1]=k=1;k<vexnum;++k){
16          for(min=Max,i=1;i<=vexnum;++i)
17              if(!vis[i]&&min>p[i]){
18                  min=p[i];
19                  t=i;
20              }
21              vis[t]=1;
22              for(i=1;i<=vexnum;++i)
23                  if(!vis[i]&&p[i]>min+m[t][i])
24                      p[i]=min+m[t][i];
25      }
26  }
27  int main()
28  {
29      int i,j,t,a,b,w;
30      while(scanf("%d",&vexnum),vexnum&&scanf("%d",&arcnum)){
31          for(i=1;i<=vexnum;++i)
32              for(j=1;j<=vexnum;++j)
33                  m[i][j]=m[j][i]=Max;
34          for(i=0;i<arcnum;++i){
35              scanf("%d%d%d",&a,&b,&w);
36              if(w<m[a][b])
37                  m[a][b]=m[b][a]=w;
38          }
39          for(i=1;i<=vexnum;++i){
40              scanf("%d",&t);
41              leader[i]=t-1;
42          }
43          for(i=1;i<=vexnum;++i)
44              for(j=1;j<=vexnum;++j){
45                  if(leader[i]!=leader[j]){
46                      if(leader[i]) m[i][j]=Max;
47                      else m[j][i]=Max;
48                  }
49              }
50          dijkstra();
51          if(p[2]<Max) printf("%d\n",p[2]);
52          else printf("-1\n");
53      }
54      system("pause");
55      return 0;
56  }