如何做自己的淘宝优惠券网站,福田商城网站建设哪家便宜,图书馆网站建设所需资料,wordpress 千易网盘正题
题目链接:https://jzoj.net/senior/#contest/show/3005/0 题目大意 nnn个点mmm条边的无向图#xff0c;有一条边的边权会变化#xff0c;qqq次变化#xff0c;每次询问最短路。 解题思路
可变边(x,y)(x,y)(x,y) 路径无非就三种 1−n1-n1−n1−x−有一条边的边权会变化qqq次变化每次询问最短路。 解题思路
可变边(x,y)(x,y)(x,y) 路径无非就三种
1−n1-n1−n1−x−y−n1-x-y-n1−x−y−n1−y−x−n1-y-x-n1−y−x−n
111和nnn都跑一次最短路就好了。 codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includecctype
#define ll long long
using namespace std;
const ll N5e510;
struct edge_node{ll to,next,w;
}a[N*2];
struct node{ll pos,dis;
};
bool operator(node x,node y)
{return x.disy.dis;}
ll read() {ll x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
ll n,m,Q,f1[N],f2[N],ls[N],s,t,tot;
bool v[N];
priority_queuenode q;
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dij(ll s,ll *f){memset(v,0,sizeof(v));q.push((node){s,0});f[s]0;while(!q.empty()){ll xq.top().pos;q.pop();if(v[x]) continue;v[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y])q.push((node){y,f[y]});}}}return;
}
int main()
{freopen(monogatari.in,r,stdin);freopen(monogatari.out,w,stdout);nread();mread();Qread();for(int i1;in;i)f1[i]f2[i]1e18;for(ll i1;im;i){ll xread(),yread(),wread();addl(x,y,w);addl(y,x,w);}dij(1,f1);dij(n,f2);sread();tread();while(Q--){ll wread(),ansf1[n];ansmin(min(f1[s]f2[t]w,f1[t]f2[s]w),ans);if(ans1e18) printf(Inf\n);else printf(%lld\n,ans);}
}
