codevs 1269 匈牙利游戲

題目大意：求次短路

數據范圍:2≤n≤20000,1≤m≤100000,1≤L≤10000

思路：spfa的時候在更新最短路的時候順便更新一下次短路就好了。

題解：

#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxn=1000000; int n,m; struct cc{int from,to,cost; }es[maxn]; int first[maxn],next[maxn]; bool vis[maxn]; int tot=0; void build(int ff,int tt,int pp) {es[++tot]=(cc){ff,tt,pp};next[tot]=first[ff];first[ff]=tot; } int dis1[maxn],dis2[maxn]; queue<int>q; void spfa(int s) {dis1[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front(); q.pop();vis[u]=0;for(int i=first[u];i;i=next[i]){int v=es[i].to;if(dis1[v]>dis1[u]+es[i].cost)//能更新最短路 {dis2[v]=dis1[v];dis1[v]=dis1[u]+es[i].cost;if(!vis[v]) {q.push(v);vis[v]=1;}}else if(dis1[v]<dis1[u]+es[i].cost)//不能更新最短路但能更新次短路 {if(dis2[v]>dis1[u]+es[i].cost){dis2[v]=dis1[u]+es[i].cost;if(!vis[v]){q.push(v);vis[v]=1;}}}else if(dis2[v]>dis2[u]+es[i].cost)//通過次短路更新次短路 {dis2[v]=dis2[u]+es[i].cost;if(!vis[v]){q.push(v);vis[v]=1;}} }} } int main() {memset(dis1,63,sizeof(dis1));memset(dis2,63,sizeof(dis2));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);build(x,y,z);}spfa(1);if(dis2[n]>1000000000){printf("-1");}else{printf("%d",dis2[n]);}return 0; }

轉載于:https://www.cnblogs.com/-feather/p/7779940.html

總結

以上是生活随笔為你收集整理的codevs 1269 匈牙利游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。