poj 3114 Countries in War(縮点+DIJK)
17208 ワード
http://poj.org/problem?id=3114
点を縮めます+DIJK点を縮めます後に重い辺があることに注意しますfloyd会TLE
View Code
点を縮めます+DIJK点を縮めます後に重い辺があることに注意しますfloyd会TLE
1 #include <iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<stdlib.h>
5 #include<algorithm>
6 #include<stack>
7 #define N 510
8 #define M 301000
9 #define INF 0xfffffff
10 using namespace std;
11 struct node
12 {
13 int u,v,next,w;
14 }edge[M];
15 int t,low[N],pre[N],sccno[N],head[N],scc,dep,ww[N][N],vis[N],dis[N];
16 int o[N][N];
17 void init()
18 {
19 t = 0;
20 memset(head,-1,sizeof(head));
21 }
22 void add(int u,int v,int w)
23 {
24 edge[t].u =u;
25 edge[t].v = v;
26 edge[t].w = w;
27 edge[t].next = head[u];
28 head[u] = t++;
29 }
30 stack<int>s;
31 void dfs(int u)
32 {
33 low[u] = pre[u] = ++dep;
34 s.push(u);
35 for(int i = head[u] ; i!=-1 ; i = edge[i].next)
36 {
37 int v = edge[i].v;
38 if(!pre[v])
39 {
40 dfs(v);
41 low[u] = min(low[u],low[v]);
42 }
43 else if(!sccno[v])
44 low[u] = min(low[u],pre[v]);
45 }
46 if(low[u]==pre[u])
47 {
48 scc++;
49 for(;;)
50 {
51 int x = s.top();s.pop();
52 sccno[x] = scc;
53 if(x==u)break;
54 }
55 }
56 }
57 void find_scc(int n)
58 {
59 scc=0;dep=0;
60 memset(low,0,sizeof(low));
61 memset(pre,0,sizeof(pre));
62 memset(sccno,0,sizeof(sccno));
63 for(int i = 1; i <= n ; i++)
64 if(!pre[i])
65 dfs(i);
66 }
67 int dijk(int st,int en,int n)
68 {
69 int i,j,k,mi;
70 memset(vis,0,sizeof(vis));
71 for(i = 1; i <= n ; i++)
72 dis[i] = o[st][i];
73 dis[st] = 0;
74 for(i = 1 ;i <= n ; i++)
75 {
76 mi = INF;
77 for(j = 1; j <= n ; j++)
78 if(!vis[j]&&dis[j]<=mi)
79 mi = dis[k=j];
80 vis[k] = 1;
81 for(j = 1; j <= n ; j++)
82 if(dis[j]>o[k][j]+dis[k])
83 dis[j] = o[k][j]+dis[k];
84 }
85 return dis[en];
86 }
87 int main()
88 {
89 int i,j,n,m,k,a,b,c,g;
90 while(cin>>n>>m)
91 {
92 if(n==0&&m==0)
93 break;
94 memset(ww,0,sizeof(ww));
95 init();
96 for(i =1; i <= m ;i++)
97 {
98 scanf("%d%d%d",&a,&b,&c);
99 add(a,b,c);
100 }
101 find_scc(n);
102 for(i = 1; i <= n ; i++)
103 for(j = 1; j <= n ;j++)
104 o[i][j] = INF;
105 for(i = 1; i <= scc ; i++)
106 o[i][i] = 0;
107 for(i = 0; i < t ; i++)
108 {
109 int u = edge[i].u,v = edge[i].v;
110 if(sccno[u]!=sccno[v])
111 {
112 o[sccno[u]][sccno[v]] = min(o[sccno[u]][sccno[v]],edge[i].w);// WA
113 }
114 }
115 scanf("%d",&k);
116 while(k--)
117 {
118 scanf("%d%d",&a,&b);
119 int xx = dijk(sccno[a],sccno[b],scc);
120 if(xx==INF)
121 printf("Nao e possivel entregar a carta
");
122 else
123 cout<<xx<<endl;
124 }
125 puts("");
126 }
127 return 0;
128 }
View Code