前几天ygp就说了，是dp+spfa，然而我居然难以理解……
看着神犇们速A这题，我不禁感到太弱了……
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int en,n,m,K,E,d[105],h[105],D[105],P,dis[105][105],f[105],dp[105];
struct Edge{
int b,v,next;
}e[40005];
struct Closed{
int p,a,b;
}close[105];
void Yuchuli(int day1,int day2){
memset(d,0,sizeof(d));
for(int i=0;i<P;i++){
if(close[i].a>day2 || close[i].b<day1)continue;
d[close[i].p]=1;
}
}
int spfa(){
memset(f,0,sizeof(f));
memset(D,0x3f,sizeof(D));
queue<int> Q;
Q.push(1);
f[1]=1;
D[1]=0;
int u,v;
while(!Q.empty()){
u=Q.front();
Q.pop();
f[u]=0;
for(int i=h[u];i;i=e[i].next){
v=e[i].b;
if(d[v])continue;
if(D[u]+e[i].v<D[v]){
D[v]=D[u]+e[i].v;
if(!f[v]){
Q.push(v);
f[v]=1;
}
}
}
}
return D[m];
}
void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
int main(){
freopen("1003.in","r",stdin);
freopen("1003.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&K,&E);
for(int i=0;i<E;i++){
int sa,sb,sc;
scanf("%d %d %d",&sa,&sb,&sc);
add(sa,sb,sc);
add(sb,sa,sc);
}
scanf("%d",&P);
for(int i=0;i<P;i++){
scanf("%d %d %d",&close[i].p,&close[i].a,&close[i].b);
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
Yuchuli(i,j);
dis[i][j]=spfa();
if(dis[i][j]<0x3f3f3f3f)dis[i][j]*=j-i+1;
//printf("%d\n",dis[i][j]);
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
dp[i]=min(dp[i],dp[j]+dis[j+1][i]+K);
}
}
printf("%d\n",dp[n]-K);
return 0;
}
水平若，代码丑，速度慢，这就是3个特点。
orz wyx秒杀这题
评论 (0)
