遥远的旅途
Description
一张有n个点，m条变的无向图，每条边有边权。
在0时刻有一个人在点1，每一次他走过一条边，消耗的时间为这条边的边权，而不能停留在原地。
现在他想知道是否存在一种方案使得他在T时刻刚好到达点n。
多组数据，case<=3,2<=N<=50,1<=M<=50,1<=T<=10^18
Solution
上上周做GDOI组时WorldWide_D说这道题是T2原题，于是就被强行安利来搞这道题了。。。
发现真的是完全背包问题的加强版~~不过思路是一样的。
先枚举一条到n的边，我们要判断有没有一种方案，使得可以走到n之后，一直走这条边直到时刻T。
那么我们设这条边边权为w，Fi,j表示到点i时刻%(2*w)为j的最小的时刻。
那么转移显然，不过会出现环，那么就把每个状态看做一个点，跑一遍spfa就好了。
然后判断状态Fn,T%(2*w)是否小于T就好了。
小于T就表示这是个可行方案，不行的话还要继续枚举。。。
设总共有K个状态，时间复杂度理论O(NK^2)（玄学spfa）
加一个玄学剪枝优化就过了。。。（反正你去写dijkstra也没问题，复杂度有保证呵）
Code
#include <cstdio>
#include <cstring>
#include <iOStream>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll dis[N],T;
int n,m,l,ty,x[N],y[N],z[N],d[N*10];
int t[N*2],next[N*2],v[N*2],last[N];
bool bz[N];
ll read() {
char ch;while (!isdigit(ch=getchar()));
ll o=ch-48;while (isdigit(ch=getchar())) o=o*10+ch-48;
return o;
}
int get(int x,int y,int z) {
return (x-1)*z+y+1;
}
void add(int x,int y,int z) {
t[++l]=y;v[l]=z;next[l]=last[x];last[x]=l;
}
void link(int w) {
memset(last,0,sizeof(last));l=0;
fo(i,1,m) fo(j,0,w-1) {
add(get(x[i],j,w),get(y[i],(j+z[i])%w,w),z[i]);
add(get(y[i],j,w),get(x[i],(j+z[i])%w,w),z[i]);
}
}
void spfa() {
memset(dis,127,sizeof(dis));dis[1]=0;
memset(bz,0,sizeof(bz));bz[1]=1;
int i=0,j=1;d[1]=1;
while (i<j) {
rep(k,d[++i])
if (dis[t[k]]>dis[d[i]]+(ll)v[k]) {
dis[t[k]]=dis[d[i]]+(ll)v[k];
if (!bz[t[k]]) {
bz[t[k]]=1,d[++j]=t[k];
if (dis[d[i+1]]>dis[d[j]]) swap(d[i+1],d[j]);
}
}
bz[d[i]]=0;
}
}
int main() {
for(ty=read();ty;ty--) {
n=read();m=read();T=read();bool pd=0;
fo(i,1,m) x[i]=read(),y[i]=read(),z[i]=read(),x[i]++,y[i]++;
fo(i,1,m) if (x[i]==n||y[i]==n) {
link(z[i]*2);spfa();
if (dis[get(n,T%(z[i]*2),z[i]*2)]<=T) {pd=1;break;}
}
if (pd) printf("Possible\n");
else printf("Impossible\n");
}
}
相关阅读
A5创业网（公众号：iadmin5）3月11日报道，近日有网友爆料，携程疑似再次出现“大数据杀熟”现象，在携程上重搜机票贵了近1500元，对
每当我们听到兴趣是成功的先导、有了兴趣，就成功了一半等哲言时，总无法深刻的领会到其中的含义，因为有时候我们往往因为背负太大的社
双拼域名在国内市场素来抢手，含义直观，是终端建站的首选域名。近日，一枚双拼域名yaoyuan.com以202021元的价格高价被秒！从含义上看，域
《遥远的救世主》是一本具有浓厚批判色彩的当代思想写实小说。就像这本小说的题目，豆豆不但告诉了我们，这个世界真正的救世
有一种遥远，是家与公司的距离。无论你选择公共交通、自驾、打车、骑车、步行还是代步，都免不了经受日常通勤之苦。通勤这件小事，不仅