思路：最短路+DP
提交：1次
题解：
$f[i]$表示到第$i$天的最小代价，我们可以预先处理出$i,j$两天之间(包括$i,j$)都可通行的最短路的代价记做$s[i][j]$，然后有$f[i]=min(f[i],f[j]+s[j+1][i]*(i-j)+W);$
#include#include #include #include #define ull unsigned long long#define ll long long#define R register intusing namespace std;#define pause (for(R i=1;i<=10000000000;++i))#define In freopen("NOIPAK++.in","r",stdin)#define Out freopen("out.out","w",stdout)namespace Fread {static char B[1<<15],*S=B,*D=B;#ifndef JACK#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)#endifinline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;} inline bool isempty(const char& ch) { return (ch<=36||ch>=127);}inline void gs(char* s) { register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));}} using Fread::g; using Fread::gs;namespace Luitaryi {const int N=25,M=110;int t,n,W,m,cnt;int vr[N*N],nxt[N*N],w[N*N],fir[N],d[N],s[M][M];ll f[N];bool vis[N],ban[N],c[N][M];inline void add(int u,int v,int ww) {vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;}inline int spfa() { memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); queue q; q.push(1); d[1]=0; vis[1]=true; while(q.size()) { R u=q.front(); q.pop(); vis[u]=false; if(ban[u]) continue; for(R i=fir[u];i;i=nxt[i]) { R v=vr[i]; if(d[v]>d[u]+w[i]) { d[v]=d[u]+w[i]; if(!vis[v]) q.push(v),vis[v]=true; } } } return d[n];}inline void main() { t=g(),n=g(),W=g(),m=g(); for(R i=1,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w); m=g(); for(R i=1,u,l,r;i<=m;++i) { u=g(),l=g(),r=g(); for(R j=l;j<=r;++j) c[u][j]=true; } for(R i=1;i<=t;++i) { memset(ban,0,sizeof(ban)); for(R j=i;j<=t;++j) { for(R u=1;u<=n;++u) ban[u]|=c[u][j]; s[i][j]=spfa(); } } for(R i=1;i<=t;++i) { f[i]=1ll*s[1][i]*i; for(R j=1;j
2019.07.21