这道题被马老板毒瘤了一下,TLE到怀疑人生
//然而BZOJ上妥妥地过了(5500ms+ -> 400ms+)
要么SPFA太玄学要么是初始化block被卡到O(n^4)
不管了,不改了
另外DP方程值得学习
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int maxn = 4e4+11;
typedef long long ll;
const int oo = 0x3f3f3f3f;
vector<int> vec[333];//block
int to[maxn<<1],nxt[maxn<<1],cost[maxn<<1],head[maxn],tot;
void init(){
memset(head,-1,sizeof head);
tot=0;
}
void add(int u,int v,int w){
to[tot]=v;nxt[tot]=head[u];cost[tot]=w;
head[u]=tot++;
swap(u,v);
to[tot]=v;nxt[tot]=head[u];cost[tot]=w;
head[u]=tot++;
}
int dis[maxn];
bool vis[maxn];
bool xx[666];
int n,m,k,e;
int spfa(int day1,int day2){
if(day1>day2)swap(day1,day2);
memset(dis,oo,sizeof dis);
memset(vis,0,sizeof vis);
memset(xx,0,sizeof xx);
for(int day=day1;day<=day2;day++){
for(int t = 0; t < vec[day].size(); t++){
xx[vec[day][t]]=1;
}
}
stack<int> que;
que.push(1);vis[1]=1;dis[1]=0;
while(!que.empty()){
int u=que.top(); que.pop();vis[u]=0;
for(int i=head[u]; ~i; i=nxt[i]){
int v=to[i],w=cost[i];
if(!xx[v]&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;
que.push(v);
}
}
}
}
return dis[m];
}
ll dp[333];
ll rec[333][333];
int main(){
scanf("%d%d%d%d",&n,&m,&k,&e);
init();
for(int i = 0; i < 333; i++) vec[i].clear();
int u,v,w,t,a,b,c;
rep(i,1,e){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
scanf("%d",&t);
rep(i,1,t){
scanf("%d%d%d",&c,&a,&b);
rep(j,a,b) vec[j].push_back(c);
}
rep(i,1,n) rep(j,1,n) rec[i][j]=1ll<<60;
rep(i,1,n) rep(j,i,n) rec[i][j]=spfa(i,j);
rep(i,1,n) dp[i]=rec[1][i]*i;
dp[0]=0;
rep(i,1,n){
rep(j,0,i-1){
dp[i]=min(dp[i],dp[j]+rec[j+1][i]*(i-j)+k);
}
}
printf("%lld\n",dp[n]);
return 0;
}