问题描述
某一天，少年邂逅了同病相连的IA。见面后，IA一把牵起少年的手，决定和他一起逃离部落，离开这个无法容身的是非之地。
要逃离部落，少年和IA就需要先选择一条耗时最少的路线，从而避免被部落的大人们抓到。部落可以大致分为N个区域，少年和IA在区域1，部落的出口设在区域N。此外部落还有M条连接两个区域道路。道路是无向的，没有一条道路的两端连接相同的区域，也没有两条道路所连接的两个区域完全相同。对于其中前(M-1)条道路，其通过时间是确定的，但最后一条道路，由于地理因素，通过其的时间会不断变化。
现在，少年和IA得知了在K个不同的时段里，通过第M条道路的时间，请您分别计算出在这K个时段中逃离部落的最少时间，以帮助他们确定行动的时刻。
输入格式
输出格式
样例输入
样例输出
数据范围
题解
先把第m条边从原图中删去，
起点为1，终点为n
设第m条边的端点分别是x,y
最优路径一定是以下三种情况之一
1->n
1->x->y->n
1->y->x->n
分别预处理1,n开始的最短路
然后O(1)回答询问即可
SPFA双端队列优化会被卡常，要用Dijkstra堆优化
还有个小优化，把k个时间段第m条边的值从小到大排序，排序后，如果在某个时间段如果最短路不经过第m条边，那么后面的时间段也不会经过第m条边，可以退出循环直接输答案。
1 #pragma GCC optimize(2) 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 #include <queue> 7 #define ll long long 8 #define pa pair<ll,int> 9 using namespace std; 10 const int maxn=500100; 11 struct node{ 12 int u,w,nex; 13 }g[1000005]; 14 struct note{ 15 int v,id; 16 }a[30005]; 17 int n,m,K,fir[500005],num; 18 ll dis[2][500005],ans[30005]; 19 bool vis[500005]; 20 priority_queue <pa,vector<pa>,greater<pa> > q; 21 bool cmp(note x,note y) 22 { 23 return x.v<y.v; 24 } 25 int read() 26 { 27 int s=0; 28 char ch=getchar(); 29 while (ch<'0' || ch>'9') ch=getchar(); 30 while (ch>='0' && ch<='9') 31 s=s*10+ch-'0',ch=getchar(); 32 return s; 33 } 34 ll min(ll x,ll y) 35 { 36 return x<y?x:y; 37 } 38 void add(int x,int y,int z) 39 { 40 g[++num].u=y; g[num].w=z; g[num].nex=fir[x]; fir[x]=num; 41 return; 42 } 43 void dijkstra(int S,int p) 44 { 45 int h=0,t=1,u,v,i; 46 for (i=1;i<=n;i++) dis[p][i]=1e15; 47 dis[p][S]=0; 48 q.push(make_pair(0,S)); 49 while (!q.empty()) 50 { 51 u=q.top().second; q.pop(); 52 for (i=fir[u];i;i=g[i].nex) 53 { 54 v=g[i].u; 55 if (dis[p][v]>dis[p][u]+g[i].w) 56 dis[p][v]=dis[p][u]+g[i].w, 57 q.push(make_pair(dis[p][v],v)); 58 } 59 } 60 return; 61 } 62 int main() 63 { 64 // freopen("a.in","r",stdin); 65 int i,j,x,y,z,p; 66 //scanf("%d%d%d",&n,&m,&K); 67 n=read();m=read();K=read(); 68 for (i=1;i<m;i++) 69 //scanf("%d%d%d",&x,&y,&z), 70 x=read(),y=read(),z=read(), 71 add(x,y,z),add(y,x,z); 72 //scanf("%d%d",&x,&y); 73 x=read();y=read(); 74 dijkstra(1,0); dijkstra(n,1); 75 for (i=1;i<=K;i++) a[i].v=read(),a[i].id=i; 76 std::sort(a+1,a+K+1,cmp); 77 for (i=1;i<=K;i++) 78 { 79 p=a[i].id; 80 ans[p]=min(dis[0][n],min(dis[0][x]+a[i].v+dis[1][y],dis[0][y]+a[i].v+dis[1][x])); 81 if (ans[p]>=1e15) ans[p]=-1; 82 if (ans[p]==dis[0][n]) 83 { 84 for (j=i+1;j<=K;j++) 85 ans[a[j].id]=ans[p]; 86 break; 87 } 88 } 89 for (i=1;i<=K;i++) 90 if (ans[i]>-1) printf("%lld ",ans[i]); 91 else printf("+Inf "); 92 return 0; 93 }