題目地址：

題解：題目意思為從起點到終點的最短路中有一條路不能通過了，求到從起點到終點的最短距離。

可以先找出從起點到終點的最短距離，并將路徑保存下來，然后枚舉最短路徑中的所有路徑，求

出從起點到終點的最短路徑中最長的一條。

?

#include<iostream> #include<string> #include<queue> using namespace std; const int maxn = 1005; const int INF = 200000000; struct node {int v,t;struct node *next; }*head[maxn],edge[maxn*maxn]; int n,m,dis[maxn],per[maxn]; bool vis[maxn]; queue<int> que; void spfa() {for(int j = 1; j <= n; j++)dis[j] = INF,vis[j] = false;;dis[1] = 0;vis[1] = true;que.push(1);while(!que.empty()){int now = que.front();que.pop();vis[now] = false;for(node *p = head[now] ; p ; p = p->next){if(dis[p->v] > dis[now] + p->t){dis[p->v] = dis[now] + p->t;per[p->v] = now;//記錄到點p->的前驅結點if(!vis[p->v]){vis[p->v] = true;que.push(p->v);}}}} } void spfa(int x,int y) {for(int i = 1; i <= n; i++)dis[i] = INF,vis[i] = false;vis[1] = true;dis[1] = 0;que.push(1);while(!que.empty()){int now = que.front();que.pop();vis[now] = false;for(node *p = head[now] ; p ; p = p->next){if((now == y && p->v == x)||(now == x && p->v == y))//路p->v到now的路不能走continue;if( dis[p->v] > dis[now] + p->t){dis[p->v] = dis[now] + p->t;if(!vis[p->v]){vis[p->v] = true;que.push(p->v);}}}} } int main() {int i;int a,b,time;while(cin >> n >> m){for(i = 1; i <= n; i++)head[i] = NULL;node *p = edge;while(m --){cin >> a >> b >> time;p->v = b;p->t = time;p->next = head[a];head[a] = p++;p->v = a; p->t = time;p->next = head[b];head[b] = p++;}per[1] = -1;spfa();int max = dis[n];for(i = n; per[i] != -1; i = per[i])//枚舉最短路中的所有路徑。{spfa(i,per[i]);if(dis[n] != INF && dis[n] > max)max = dis[n];}printf("%d\n",max);}return 0; }

?

轉載于:https://www.cnblogs.com/LUO257316/archive/2012/09/06/3220855.html

總結

以上是生活随笔為你收集整理的1595 hdu find the longest of the shortest的全部內容，希望文章能夠幫你解決所遇到的問題。

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