正题

题目链接:https://jzoj.net/senior/#main/show/3890

---

题目大意

$n$个点$m$条边的图，询问是否有$1$到$n$长度为$T$的路径。

---

解题思路

让$W$等于连接$1$的最小权值的两倍，然后用$f_{i,j}$表示到第$i$个点是否有权值$\%W=j$。然后用$f_{i,T\%W}$判断就好了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=55; struct edge_node{ll to,next,w; }a[N*4]; ll n,m,k,T,tot,W,ls[N*21000]; queue<int> q,qw; bool v[N][21000]; void addl(ll x,ll y,ll w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w; } void SPFA(){memset(v,0,sizeof(v));q.push(1);qw.push(0);v[1][0]=1;while(!q.empty()){ll x=q.front(),w=qw.front();q.pop();qw.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to,yw=(w+a[i].w)%W;if(!v[y][yw]){v[y][yw]=1;q.push(y);qw.push(yw);}}} } int main() {scanf("%lld",&T);while(T--){tot=0;W=2147483647;memset(ls,0,sizeof(ls));scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=m;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);x++;y++;addl(x,y,w);addl(y,x,w);}for(ll i=ls[1];i;i=a[i].next)W=min(W,a[i].w*2);SPFA();if(v[n][k%W]) printf("Possible\n");else printf("Impossible\n");} }

总结

以上是生活随笔为你收集整理的jzoj3890-长途旅行【同余最短路】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。