SPFA--P3905 道路重建

破坏掉一些路径，修复他的代价就是该路径的长度，没有破坏的路径，修复它的代价是0（*链式前向星建图）

SPFA求最短路：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <queue>
 6 using namespace std;
 7 int n,m,d;
 8 int a,b;
 9 int x,y;
10 int dis[10000];
11 bool vis[10000];
12 bool mark[1000][1000];
13 struct node
14 {
15     int x,y,w;
16 }edge[10000];
17 struct ask
18 {
19     int w;
20     int to;
21     int next;
22 }ed[10000];
23 int head [10000];
24 int tot =0;
25 void add (int u,int v,int w)
26     {
27       ed[++tot].w=w;
28       ed[tot].to=v;
29       ed[tot].next=head[u];
30       head[u]=tot;
31 }
32 void SPFA(int s)
33 {
34       queue<int> q;
35         for(int i=1;i<=n;i++){//初始化， 
36             dis[i]=0x7fffffff;
37             vis[i]=0;
38         }
39         q.push(s);//放入起点 
40         dis[s]=0;//自己到自己为0； 
41         vis[s]=1;
42         while(!q.empty()){ 
43             int u=q.front();
44             q.pop();vis[u]=0;//弹出队首 
45             for(int i=head[u];i;i=ed[i].next){
46                 int v=ed[i].to;

48                 if(dis[v]>dis[u]+ed[i].w){
49                     dis[v]=dis[u]+ed[i].w;
50                     if(!vis[v]){
51                         vis[v]=1;
52                         q.push(v);//重新放入； 
53                     }
54                 }
55             }
56         }
57 }
58 int main()
59 {
60     scanf ("%d",&n);
61     scanf ("%d",&m);
62     for (int i = 1;i <= m;i++)
63     {
64         scanf ("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
65     }
66     scanf ("%d",&d);
67     for (int i = 1;i <= d;i++)
68     {
69         scanf ("%d%d",&x,&y);
70         mark[x][y]=1;
71         mark[y][x]=1;
72     }
73     scanf ("%d%d",&a,&b);
74     for (int i = 1;i <= m;i++)
75     {
76         if (mark[edge[i].x][edge[i].y]==1)
77         {
78             add(edge[i].x,edge[i].y,edge[i].w);    
79             add(edge[i].y,edge[i].x,edge[i].w);
80         }
81         else 
82         {
83             add(edge[i].x,edge[i].y,0);
84             add(edge[i].y,edge[i].x,0);     
85         }
86     }
87     SPFA(a);
88     cout<<dis[b]<<endl;
89     return 0;
90 }