# [BZOJ1003]&&[ZJOI2006] 物流运输 trans

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

32

BZOJ 1003

## 代码 Code

DP+SPFA。

$f[i]=Min \lbrace f[j]+(i-j)*cost[j,i]+k \rbrace ,0 \leq j < i \\\ f[0]=-k$

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k,z,y,x;
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct edge
{
int to,next,val;
}e[505];
bool used[25];
int cnt=0;
deque <int> q;
inline void ins(int u,int v,int w)
{
}
int spfa(int x,int y)
{
int i,j,t,u,v,w;
int s=1;
memset(used,false,sizeof(used));
while (!q.empty()) q.pop_front();
for (i=1;i<=m;i++) dis[i]=inf;
used[s]=true;dis[s]=0;q.push_back(s);
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
{
v=e[i].to;w=e[i].val;
if (c[v][y]-c[v][x]==0 && dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty() && dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[m];
}
int main()
{
memset(c,0,sizeof(c));
for (i=1;i<=n;i++) f[i]=inf;
for (i=1;i<=E;i++)
{
ins(x,y,z);
ins(y,x,z);
}
for (i=1;i<=p;i++)
{
for (j=y;j<=z;j++) c[x][j]=1;
}
for (i=1;i<=m;i++) for (j=1;j<=n;j++) c[i][j]+=c[i][j-1];
f[0]=-k;
for (i=1;i<=n;i++)
{
for (j=0;j<i;j++)
{
t=spfa(j,i);
if (t!=inf) f[i]=min(f[i],f[j]+(i-j)*t+k);
}
}
printf("%d\n",f[n]);
return 0;
}