题目描述

N (1 <= N <= 100)个点，M (1 <= M <= 10,000)条双向通行的边，每条边有一个长度值。两点之间若有边，则只有一条边。任意点对之间都有通路。FJ总是行走长度最短的路径。 现在求：若可任意选择一条边，把它的长度*2，则从编号1的点到编号N的点之间的最短距离，最长可以增加多少距离。

输入格式

第一行: 两个整数 N,M. 行 2..1+M:行 j+1表示第 j条双向边情况，aj bj Lj (端点编号及边长 1<=lj<=1,000,000，整数).

输出格式

1行：最短路最大增加长度

样例输入

5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2

样例输出

2

题目分析

刚刚写完最短路径上边权减半问题就看到这题，可惜不能直接套模板，因为这题求的是最大。 既然如此就随便暴力搞搞吧。 跑一次Dijkstra求出最短路，然后枚举所有最短路上的边，将边权*2再跑一次Dijkstra。 我的代码中有一个小技巧：在第一次Dijkstra时就保存路径path以及在路径上的点和前驱结点相连的边的邻接表编号，因此可以方便地修改边权。

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=505; //数组范围 struct Edge { //前向星 int from,to,dist; } E[50005]; struct HeapNode { int d,u; //u为当前结点 bool operator < (HeapNode a) const { return d>a.d; } }; struct Dijkstra { int n,m; vector<Edge> edges; //邻接表 vector<int> G[maxn]; //记录每个结点可以到达的结点 bool vst[maxn]; int dist[maxn],path[maxn],pathe[maxn]; //使用path记录最短路 void init(int n) { this->n=n; for(int i=1; i<=n; i++)G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int dist) { edges.push_back((Edge) { from,to,dist }); m=edges.size(); G[from].push_back(m-1); } void main(int s) { //核心算法 priority_queue<HeapNode> Q; for(int i=1; i<=n; i++)dist[i]=0x7fffffff/2; dist[s]=0; path[s]=s; memset(vst,0,sizeof(vst)); Q.push((HeapNode) { 0,s }); while(!Q.empty()) { HeapNode Now=Q.top(); Q.pop(); if(vst[Now.u])continue; vst[Now.u]=1; for(int i=0; i<G[Now.u].size(); i++) { Edge& e=edges[G[Now.u][i]]; //边的信息 int Next=e.to; if(dist[Next]>dist[Now.u]+e.dist) { dist[Next]=dist[Now.u]+e.dist; path[Next]=Now.u; pathe[Next]=G[Now.u][i]; Q.push((HeapNode) { dist[Next],Next }); } } } } void Output(int x) { if(path[x]==x) { cout<<x<<" "; return; } Output(path[x]); cout<<x<<" "; } } ; Dijkstra dij; int n,m,ans=-0x7fffffff/2,Ans,path[maxn],pathe[maxn]; int main() { n=Get_Int(); m=Get_Int(); dij.init(n); for(int i=1; i<=m; i++) { int x=Get_Int(),y=Get_Int(),v=Get_Int(); dij.AddEdge(x,y,v); dij.AddEdge(y,x,v); } dij.main(1); Ans=dij.dist[n]; memcpy(path,dij.path,sizeof(dij.path)); memcpy(pathe,dij.pathe,sizeof(dij.pathe)); for(int i=n; i!=1; i=path[i]) { Edge& e=dij.edges[pathe[i]]; e.dist*=2; dij.main(1); ans=max(ans,dij.dist[n]-Ans); e.dist/=2; } printf("%d\n",ans); return 0; }