从前，在一个王国中，在n个城市间有m条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有d条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市A和B之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使A与B之间的连接恢复，并要求修复的道路长度最小。
输入文件第一行为一个整数n（2<n≤100）,表示城市的个数。这些城市编号从1到n。
第二行为一个整数m（n−1≤m≤2n(n−1)），表示道路的数目。
接下来的m行，每行3个整数i,j,k（1≤i,j≤n,i≠j,0<k≤100），表示城市iii与jjj之间有一条长为k的道路相连。
接下来一行为一个整数d（1≤d≤m），表示战后被破坏的道路的数目。在接下来的d行中，每行两个整数i和j，表示城市iii与jjj之间直接相连的道路被破坏。
最后一行为两个整数A和B，代表需要恢复交通的两个重要城市。
输出文件仅一个整数，表示恢复A与B间的交通需要修复的道路总长度的最小值。
破坏掉一些路径，修复他的代价就是该路径的长度，没有破坏的路径，修复它的代价是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; 47 if (vis[v])continue; 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 }
原文：https://www.cnblogs.com/very-beginning/p/12294522.html