题目链接
http://acm.fzu.edu.cn/problem.php?pid=2298
题意
给定n个点，m条边。
每个点有一个权值，表示从该点离开必须满足在该点的时刻在范围[0,ai),[2*ai,3*ai),…,[2k*ai,(2k+1)*ai).
求从s点到t点的最短时间。
解题
以时间为距离指标，求s到t的最短路即可。
注意在点u可能需要停留一段时间。这段时间应累加到抵达下一个点的时间。
AC代码
#include<cstdio>
#include<algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;const int maxn=1e3+7;
const int maxe=1e6+7;
int a[maxn];
int si,ei;
struct edge
{int to,next,w;
}e[maxe<<1];
int head[maxn],cnt;
void init()
{memset(head,-1,sizeof(head));cnt=-1;
}
void add_edge(int u,int v,int w)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}
bool vis[maxn];
int d[maxn];
void spfa()
{queue<int> que;memset(d,0x3f,sizeof(d));que.push(si);d[si]=0;vis[si]=true;int now;while(!que.empty()){int num=que.front();que.pop();vis[num]=false;int x=d[num]/a[num];now=d[num];if(x%2==1) now=(x+1)*a[num];for(int i=head[num];i!=-1;i=e[i].next){int v=e[i].to;int w=e[i].w;if(d[v]>now+w){d[v]=now+w;if(!vis[v])//没有负环可以不用vis{vis[v]=true;que.push(v);}}}}cout<<d[ei]<<endl;
}
int main()
{ios::sync_with_stdio(false);int T;cin>>T;while(T--){int n,m;cin>>n>>m;init();for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add_edge(u,v,w);add_edge(v,u,w);}cin>>si>>ei;memset(vis,false,sizeof(vis));spfa();}return 0;
}