BZOJ1003(ZJOI 2006) [물류 운송] - 최단로 + DP
[문제풀이 보고]
gi, j를 정의하면 i~j 사이의 가장 짧은 경로를 나타낸다.
fi는 i의 총 원가를 나타낸다.
방정식fi=fj+K+gj+1, i∗(i-j)
#include
#include
#include
#define LL long long
using namespace std;
const int maxn=105,maxm=805,maxv=25;
int T,n,P,m,D,tot,g[maxn][maxn],que[maxn],dst[maxn],lnk[maxn],son[maxm],nxt[maxm],w[maxm];
bool vis[maxn],pd[maxn],flg[maxn][maxv];
LL f[maxn];
inline char nc()
{
static char buf[100000],*l,*r;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
if (l==r) return EOF; return *l++;
}
inline int Read()
{
int res=0; char ch=nc();
while (ch<'0'||ch>'9') ch=nc();
while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=nc();
return res;
}
void Add(int x,int y,int z) {w[++tot]=z; son[tot]=y; nxt[tot]=lnk[x]; lnk[x]=tot;}
int Spfa(int s,int t)
{
memset(dst,63,sizeof(dst));
memset(pd,1,sizeof(pd));
memset(vis,0,sizeof(vis));
for (int i=s; i<=t; i++)
for (int j=1; j<=n; j++)
if (!flg[i][j]) pd[j]=0;
int hed=0,til=1; que[1]=1; dst[1]=0; vis[1]=1;
while (hed!=til)
{
int x=que[hed=(hed+1)%maxn]; vis[x]=0;
for (int j=lnk[x]; j; j=nxt[j])
if (pd[son[j]]&&dst[x]+w[j]<=dst[son[j]])
{
dst[son[j]]=dst[x]+w[j];
if (!vis[son[j]])
{
vis[son[j]]=1; que[til=(til+1)%maxn]=son[j];
if (dst[que[til]]1)%maxn]]) swap(que[til],que[(hed+1)%maxn]);
}
}
}
return dst[n];
}
int main()
{
freopen("1003.in","r",stdin);
freopen("1003.out","w",stdout);
T=Read(); n=Read(); P=Read(); m=Read(); tot=0;
for (int i=1,x,y,z; i<=m; i++) x=Read(),y=Read(),z=Read(),Add(x,y,z),Add(y,x,z);
D=Read(); memset(flg,1,sizeof(flg));
for (int i=1; i<=D; i++)
{
int x=Read(),s=Read(),t=Read();
for (int j=s; j<=t; j++) flg[j][x]=0;
}
for (int i=1; i<=T; i++)
for (int j=1; j<=T; j++) g[i][j]=Spfa(i,j);
for (int i=1; i<=T; i++)
{
f[i]=(LL)g[1][i]*i;
for (int j=1; j1][i]*(i-j));
}
printf("%lld
",f[T]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVa10986_Sending email(최단락)(소백서 도론 테마)문제 풀이 보고서 생각: 벌거벗은 최단로. Problem E Sending email Time Limit: 3 seconds "A new internet watchdog is creating a stir in Spr...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.