sdut2493Constructing Roads

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2493

题意：对于一个给定的无向图，求其中有一条边的边权可以减半的情况下从 A 点到 B 点的最短路。
做法：可以用spfa求出 A
到所有点的最短路 dis 和 B 到所有点的最短路 dis1 。然后枚举所有边（u,v）,找出最小的dis[ u ] + w(u,v) / 2 +
dis1[ v ] 即可，如果A、B不可达，输出“No solution”。

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 #define INF 0x3f3f3f
 8 struct node
 9 {
10     int u,v,next,w;
11 }men[100010];
12 struct node o[50010];
13 int first[1010],t;
14 void init()
15 {
16     t = 0;
17     memset(first,-1,sizeof(first));
18 }
19 void add(int u,int v,int w)
20 {
21     men[t].v = v;
22     men[t].w = w;
23     men[t].next = first[u];
24     first[u] = t;
25     t++;
26 }
27 void spfa(int n,int s,int *dis)
28 {
29     int i,j,k;
30     int f[1010];
31     memset(f,0,sizeof(f));
32     for(i = 1; i <= n ; i++)
33     dis[i] = INF;
34     queue<int>q;
35     dis[s] = 0;
36     q.push(s);
37     while(!q.empty())
38     {
39         int v = q.front();
40         q.pop();
41         f[v] = 0;
42         for(i = first[v] ; i != -1 ; i = men[i].next)
43         {
44             int tv = men[i].v;
45             int tw = men[i].w;
46             if(dis[tv]>dis[v]+tw)
47             {
48                 dis[tv] = dis[v]+tw;
49                 if(!f[tv])
50                 {
51                     q.push(tv);
52                     f[tv] = 1;
53                 }
54             }
55         }
56     }
57 }
58 int main()
59 {
60     int n,m,u,v,w,i,j,k,a,b;
61     int dis1[1010],dis2[1010];
62     while(cin>>n>>m)
63     {
64         init();
65         for(i = 1; i <= m ; i++)
66         {
67             cin>>o[i].u>>o[i].v>>o[i].w;
68             add(o[i].u,o[i].v,o[i].w);
69             add(o[i].v,o[i].u,o[i].w);
70         }
71         cin>>a>>b;
72         spfa(n,a,dis1);
73         spfa(n,b,dis2);
74         if(dis1[b]==INF)
75         {
76             cout<<"No solution\n";
77             continue;
78         }
79         int mi = INF;
80         for(i = 1; i <= m ; i++)
81         {
82             mi = min(mi,dis1[o[i].u]+dis2[o[i].v]+o[i].w/2);
83             mi = min(mi,dis1[o[i].v]+dis2[o[i].u]+o[i].w/2);
84         }
85         if(mi<INF)
86         cout<<mi<<endl;
87         else
88         cout<<"No solution\n";
89     }
90     return 0;
91 }