这道题算是一道分层图的最短路：按照天数对图进行分层，并且，在day-1层和day层，每个相连的节点(u,v)都有一条权值为w[day]的边，表示从day-1天在u到day天到v需要w[day]的路费。这样考虑的话，我们可以把每个节点拆成k个，然后每个节点u的第day-1个连到v节点的第day个，边权为w[day]，构建一个图然后跑最短路。
但是，蒟蒻不会拆点(划掉)。由于每次连点都是从u的day-1转移到v的day，因此，考虑在松弛操作上做手脚，达到类似分层的效果：把松弛操作改为
if(dis[v][day+1]>dis[u][day]+e[i].w+a[day+1]) dis[v][day+1]=dis[u][day]+e[i].w+a[day+1]
另外，需要特判一个条件：因为k天后就追不到了，因此，还需要：
if(day+1>k) continue;
不拿该状态去更新。
另：蒟蒻表示一开始并不是这么想的，没有考虑分层的问题。
错误代码
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=((ans%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxm=1e4+10,maxn=1e3+10;
int n,m,k;
struct Edge{
int to,next,w;
}e[maxm<<1];
int head[maxn],cnt;
int a[maxn];
void add(int x,int y,int w){
e[cnt].to=y;
e[cnt].w=w;
e[cnt].next=head[x];
head[x]=cnt++;
}
struct node{
int u,dis,t,cost;
node(int uu,int dd,int tt){
u=uu;
dis=dd;
t=tt;
cost=(t>k?inf:dis+a[t]);
}
};
auto cmp=[](const node&a,const node&b){
return a.cost>b.cost;
};
priority_queue<node,vector<node>,decltype(cmp)> que(cmp);
int dis[maxn],vis[maxn];
int solve(){
memset(dis,inf,sizeof(dis));
dis[1]=0;
que.push(node(1,0,1));
while(!que.empty()){
node now=que.top();que.pop();
int u=now.u;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(dis[v]>(now.t<=k?dis[u]+e[i].w+a[now.t]:inf)){
dis[v]=dis[u]+e[i].w+a[now.t];
if(!vis[v]) que.push(node(v,dis[v],now.t+1));
}
}
}
if(dis[n]==inf) return -1;
else return dis[n];
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//===========================================================
memset(head,-1,sizeof(head));
read(n),read(m),read(k);
rep(i,1,m){
int x,y,c;read(x),read(y),read(c);
add(x,y,c),add(y,x,c);
}
rep(i,1,k) read(a[i]);
write(solve());
//===========================================================
return 0;
}hack数据是：
6 8 2
1 2 499
2 3 499
3 4 490
1 3 1
4 6 1
1 5 1000
5 6 4999
3 5 5
0 1
原因是：因为图没有分层，所以5点被1——3——5更新完距离为6后，又被1——5路径转移过来的node更新节点6的距离，导致用的是dis[5]=6，但天数没有匹配上。因此，想到分层。
AC代码
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=((ans%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
//#define int ll
ll INF=inf;
const int maxm=1e4+10,maxn=1e3+10;
int n,m,k;
struct Edge{
int to,next,w;
}e[maxm<<1];
int head[maxn],cnt;
int a[maxn];
void add(int x,int y,int w){
e[cnt].to=y;
e[cnt].w=w;
e[cnt].next=head[x];
head[x]=cnt++;
}
struct node{
int u,dis,t;
node(int uu,int dd,int tt){
u=uu;
dis=dd;
t=tt;
}
};
auto cmp=[](const node&a,const node&b){
return a.dis>b.dis;
};
priority_queue<node,vector<node>,decltype(cmp)> que(cmp);
int dis[maxn][20],vis[maxn][20];
/*int solve(){
rep(i,0,n){
dis[i]=INF;
}
//memset(dis,inf,sizeof(dis));
dis[1]=0;
que.push(node(1,0,1));
while(!que.empty()){
node now=que.top();que.pop();
int u=now.u;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(dis[v]>(now.t<=k?dis[u]+e[i].w+a[now.t]:INF)){
dis[v]=dis[u]+e[i].w+a[now.t];
if(v==n&&dis[v]==5007){
cerr<<now.t<<endl;
}
if(!vis[v]) que.push(node(v,dis[v],now.t+1));
}
}
}
if(dis[n]==INF) return -1;
else return dis[n];
}*/
ll solve(){
memset(dis,inf,sizeof(dis));
dis[1][0]=0;
que.push(node(1,0,0));
while(!que.empty()){
node now=que.top();que.pop();
int u=now.u;
if(vis[u][now.t]) continue;
//cerr<<"ok"<<endl;
vis[u][now.t]=1;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(now.t+1>k) continue;
if(dis[v][now.t+1]>dis[u][now.t]+e[i].w+a[now.t+1]){
dis[v][now.t+1]=dis[u][now.t]+e[i].w+a[now.t+1];
que.push(node(v,dis[v][now.t+1],now.t+1));
}
}
}
int ans=inf;
rep(i,1,k){
ans=min(ans,dis[n][i]);
}
if(ans==inf) return -1;
return ans;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//===========================================================
memset(head,-1,sizeof(head));
read(n),read(m),read(k);
rep(i,1,m){
int x,y,c;read(x),read(y),read(c);
add(x,y,c),add(y,x,c);
}
rep(i,1,k) read(a[i]);
//rep(i,1,k) a[i]+=a[i-1];
write(solve());
//===========================================================
return 0;
}
京公网安备 11010502036488号