poj 3114(强连通缩点+SPFA)

思路：题目要求很简单，就是求两点之间的花费的最短时间,不过有一个要求：如果这两个city属于同一个国家，则花费时间为0。如何判断一个是属于同一个国家呢？就要缩点了，这样属于同一个强连通分量的点就是属于同一个国家了。然后就是SPFA求最短路。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stack>
 6 #include<vector>
 7 #include<queue>
 8 using namespace std;
 9 #define MAXN 555
10 #define inf 1<<30
11 
12 struct Edge{
13     int v,w;
14     Edge(int vv,int ww):v(vv),w(ww){}
15 };
16 
17 int dfn[MAXN],low[MAXN],color[MAXN];
18 bool mark[MAXN];
19 int dist[MAXN];
20 int n,m,k,cnt,_count;
21 
22 vector<vector<Edge> >map;
23 stack<int>S;
24 
25 void Tarjan(int u)
26 {
27     dfn[u]=low[u]=++cnt;
28     mark[u]=true;
29     S.push(u);
30     for(int i=0;i<map[u].size();i++){
31         int v=map[u][i].v;
32         if(dfn[v]==0){
33             Tarjan(v);
34             low[u]=min(low[u],low[v]);
35         }else if(mark[v]){
36             low[u]=min(low[u],dfn[v]);
37         }
38     }
39     if(low[u]==dfn[u]){
40         int v;
41         _count++;
42         do{
43             v=S.top();
44             S.pop();
45             mark[v]=false;
46             color[v]=_count;
47         }while(u!=v);
48     }
49 }
50 
51 int SPFA(int st,int ed)
52 {
53     for(int i=1;i<=n;i++)dist[i]=inf;
54     dist[st]=0;
55     queue<int>Q;
56     Q.push(st);
57     while(!Q.empty()){
58         int u=Q.front();
59         Q.pop();
60         mark[u]=false;
61         for(int i=0;i<map[u].size();i++){
62             int v=map[u][i].v,w=map[u][i].w;
63             if(color[u]==color[v])w=0;
64             if(dist[u]+w<dist[v]){
65                 dist[v]=dist[u]+w;
66                 if(!mark[v]){ mark[v]=true;Q.push(v); }
67             }
68         }
69     }
70     return dist[ed]<inf;
71 }
72 
73 int main()
74 {
75     int u,v,w;
76     while(~scanf("%d",&n)&&n){
77         scanf("%d",&m);
78         map.clear();map.resize(n+2);
79         while(m--){
80             scanf("%d%d%d",&u,&v,&w);
81             map[u].push_back(Edge(v,w));
82         }
83         cnt=_count=0;
84         memset(dfn,0,sizeof(dfn));
85         memset(mark,false,sizeof(mark));
86         for(int i=1;i<=n;i++){
87             if(dfn[i]==0)Tarjan(i);
88         }
89         scanf("%d",&k);
90         while(k--){
91             scanf("%d%d",&u,&v);
92             if(SPFA(u,v))printf("%d
",dist[v]);
93             else puts("Nao e possivel entregar a carta");
94         }
95         puts("");
96     }
97     return 0;
98 }

View Code