题目大意：
已知农夫从 1 走到 N 点，一定走的是最短路。问你将某条路的长度变为其两倍后，农夫从 1 走到 N 点的路程最大增加多少，输出最大增量。
分析：
1、很显然，如果增大某条路长度会使得最短路增加，那么这条路必为原先最短路径上的某条路。
2、故只需要记录边的 id ，然后依次枚举该条路长度翻倍后的最短路径，然后取与一开始最短路的差值的最大值即可。
3、记得用 id[] 存储路径编号，然后要分别更改这条路径两个方向的边的值（因为是无向边）。
4、时间复杂度应该是 N * M * logM ，本题大约为 107 ，1s 应该够了。
代码如下：
#define IO freopen("test.in","r",stdin),freopen("test.out","w",stdout) #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <cassert> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define inf 0x3f3f3f3f #define maxn 108 typedef pair<int,int> P; int n,m,cnt; int head[maxn],dist[maxn],pre[maxn],id[maxn],a[maxn]; bool vis[maxn]; struct Edge { int to; int val; int next; }edge[10008]; inline void add(int u,int v,int w) { edge[++cnt].to=v; edge[cnt].val=w; edge[cnt].next=head[u]; head[u]=cnt; return; } int dijkstra() { for(int i=1;i<=n;i++) dist[i]=inf,vis[i]=false; priority_queue<P,vector<P>,greater<P> > q; while(!q.empty()) q.pop(); q.push(make_pair(0,1)); dist[1]=0; while(!q.empty()) { int u=q.top().second,t=q.top().first; q.pop(); if(vis[u]) continue; if(u==n) return dist[n]; vis[u]=true; for(int i=head[u];i;i=edge[i].next){ int v=edge[i].to; if(dist[v]>dist[u]+edge[i].val){ dist[v]=dist[u]+edge[i].val; pre[v]=u,id[v]=i; q.push(make_pair(dist[v],v)); } } } return dist[n]; } int main() { //IO; scanf("%d%d",&n,&m); int A,B,C; while(m--) { scanf("%d%d%d",&A,&B,&C); add(A,B,C),add(B,A,C); } int s=dijkstra(); int x=n; cnt=0; while(id[x]){ a[++cnt]=id[x]; x=pre[x]; } int ans=-1; for(int i=1;i<=cnt;i++){ if(a[i]%2==0){ edge[a[i]-1].val*=2,edge[a[i]].val*=2; int res=dijkstra(); ans=max(ans,res-s); edge[a[i]-1].val/=2,edge[a[i]].val/=2; } else{ edge[a[i]].val*=2,edge[a[i]+1].val*=2; int res=dijkstra(); ans=max(ans,res-s); edge[a[i]].val/=2,edge[a[i]+1].val/=2; } } printf("%d ",ans ); }