长途旅行

图论 最短路

题面

给出一无向图，询问从$1$号点出发，能否在恰好走的距离为$T$时，到达$n$号点。（可重复经过点和边）

• 对于$30pts$ $T\leq10^4$
• 对于另外$30pts$ $n\leq5,m\leq10$
• 对于$100pts$ $n\leq50,m\leq100,w\leq10^4,T\leq10^{18}$

解析

$T\leq10^4$

$vis[u][len]$标记该状态是否走过，记搜。

$n\leq5,m\leq10$

注意到我们似乎很明确他重复走的路线。
于是$Pre()$一下，把$T$变小。

il void Pre()
{
  mod=10000;
  Predfs(1,0,0);//找一条从起点到终点的路线,ysn表路线长度
  re ll yl=(t-mod)/ysn;
  yl-=yl%2;//保证这条路多走了偶数遍
  t-=yl*ysn;
  return;
}

接下来$30pts$记搜即可。

$T\leq10^{18}$

$T$能搞成这么大，直接标$vis$空间时间一起炸飞。
但是，每个点有$T$个状态，这$T$个状态都是有价值的吗?
如果到点$u$的路径上有一只大小为$k$的环，那么假设$vis[u][len]=1$，则$vis[u][len+kq]=1$（$q\in N^*$)
那每个点设$k$个状态不就成了，装作距离$qk$不存在的样子。
但我们实际上还是要统计距离来和$T$比较，这点应存在数组中。
于是$vis[u][len]$转型为$dp[u][len]$,记录到该点的实际距离，且该数组满足性质$dp[u][len]=len+kq(k\in N^*)$。。
但距离再长些也不过是多走几圈环，我们还是记最短距离吧。
于是，我们期望着$dp[n][T]$，不不不，是$dp[n][T\%k]$的值应当小于等于$T$（小于$T$，我们再走几圈环就可以了）。

于是这个环在哪？
根据以上分析，从点$1$必须能到达这个环，除此以外具有任意性。
那就找连接$1$的一条边吧。
为了使状态量最少，这条边应取最短边。

(为了卡常数，我交换了dp数组的两维）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=500,mod=10000;
int T,n,m,cnt,h[N],f=0,ysn,d;
ll t,dp[20005][105];
bool vis[20005][105];
struct Edge{int to,nxt,w;}e[N<<1];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
struct node{int u,len,w;bool operator < (const node &o) const {return w>o.w;}};
priority_queue<node>Q;
il void SPFA()
{
  memset(dp,63,sizeof(dp));memset(vis,0,sizeof(vis));
  Q.push((node){1,0,0});dp[0][1]=0;
  while(!Q.empty())
    {
      re node now=Q.top();Q.pop();re int u=now.u,len=now.len%d,w=now.w;
      for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to,lenn=(len+e[i].w)%d;
      if(dp[lenn][v]>dp[len][u]+e[i].w)
        {
          dp[lenn][v]=dp[len][u]+e[i].w;
          if(!vis[lenn][v]) vis[lenn][v]=1,Q.push((node){v,lenn,dp[lenn][v]});
        }
    }
      vis[len][u]=0;
    }
}
int main()
{
  freopen("travel.in","r",stdin);
  freopen("travel.out","w",stdout);
  T=gi();
  while(T--)
    {
      n=gi();m=gi();t=gi();
      memset(h,-1,sizeof(h));cnt=0;
      fp(i,1,m)
      {
        re int u=gi()+1,v=gi()+1,w=gi();
        add(u,v,w);add(v,u,w);
      }
      d=1e9;
      for(re int i=h[1];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v^1) d=min(d,e[i].w);
    }
      d<<=1;
      SPFA();
      puts(dp[t%d][n]<=t?"Possible":"Impossible");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}