wikioi 1021 玛丽卡

这题挺有意思的，虽然比较水，但是让我想起来那次百度or腾讯的一道最大流的题目，很给力，也是对最后找边进行优化，不过这题比那题简单多了，找出最短路，然后对最短路上的变进行一下标记，最后找边的时候只招最短路上的边就可以了。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 #include <vector>
 7 #include <set>
 8 #include <queue>
 9 #include <stack>
10 #define loop(s,i,n) for(i = s;i < n;i++)
11 #define cl(a,b) memset(a,b,sizeof(a))
12 using namespace std;
13 int vis[1005],pre[1005],dis[1005];
14 struct edge
15 {
16     int u,v,w,next,id;
17 }edges[1000*1005];
18 
19 int head[1005];
20 int cnt;
21 void addedge(int u,int v,int w,int id)
22 {
23     edges[cnt].u = u;
24     edges[cnt].v = v;
25     edges[cnt].w = w;
26     edges[cnt].id = id;
27     edges[cnt].next = head[u];
28     head[u] = cnt;
29     cnt++;
30 }
31 void init()
32 {
33     cnt = 0;
34     cl(head,-1);
35 }
36 int spfa(int n,int flag)
37 {
38     int i;
39     loop(0,i,n+1)
40     vis[i] = 0,dis[i] = 1000*1000+50;
41     queue<int> q;
42     q.push(1);
43     vis[1] = 1;
44     dis[1] = 0;
45     pre[1] = -1;
46     while(!q.empty())
47     {
48         int u,v;
49         u = q.front();
50         q.pop();
51         vis[u] = 0;
52         for(int i = head[u];i != -1;i = edges[i].next)
53         {
54             if(edges[i].id == flag)
55             continue;
56             v= edges[i].v;
57             if(dis[v] > edges[i].w+dis[u])
58             {
59                 dis[v] = edges[i].w+dis[u];
60                 pre[v] = i;
61                 if(!vis[v])
62                 q.push(v),vis[v] = 1;
63             }
64         }
65     }
66     return dis[n];
67 }
68 int main()
69 {
70     int n,m;
71     scanf("%d %d",&n,&m);
72     {
73         int i,j;
74         int u,v,w;
75         init();
76         for(i = 1;i <= m;i++)
77         scanf("%d %d %d",&u,&v,&w),addedge(u,v,w,i),addedge(v,u,w,i);
78         int ans;
79         ans = -1;
80         spfa(n,0);
81         for(i = pre[n];i != -1 ;i = pre[edges[i].u])
82         {
83             int leap;
84             leap = edges[i].id;
85             ans = max(ans,spfa(n,leap));
86         }
87         printf("%d
",ans);
88     }
89     return 0;
90 }

View Code