【题目描述】 有N个标号为0~N-1的车站，0时刻在0号车站，要在T时间从0号点到达N-1号点。有M种乘车方式，乘车方式用(A,B,LEAVE,TIME,COST)描述，表示可在时刻leave时刻从A出发，经过时间TIME到达B，代价是COST。规定如果想使用在时刻X由A出发，必须在X时刻之前到达A，而在时刻0有0号车站出发是可以的。若可以到达，输出最小代价，否则输出-1。 【输入格式】 第1行，三个正整数N,T,M 第2行~M+1行：每行5个整数：A,B,LEAVE,TIME,COST 【输出格式】 一个数，如题所述。 【样例输入】 3 8 2 0 1 0 4 3 1 2 5 3 4 【样例输出】 7 【数据范围】 0<=A<=N-1,0<=B<=N-1 0<=LEAVE<=10000 1<=TIME<=10000 1<=COST<=10^6 1<=N<=100 【分析】 设f[i][j]表示前i分钟走到j车站的最小代价，则最后应输出f[t+1][n-1]。
#include<bits/stdc++.h>using namespace std;const int maxn=100;struct Edge{ int a,b,leave,reach,cost;}trans[maxn+5];int n,t,m;int f[10005][maxn+5];int main(){ scanf("%d%d%d",&n,&t,&m); for (int i=1;i<=m;i++) scanf("%d%d%d%d%d",&trans[i].a,&trans[i].b,&trans[i].leave,&trans[i].reach,&trans[i].cost),trans[i].reach+=trans[i].leave+1; for (int i=0;i<=n;i++) for (int j=0;j<=t+1;j++) f[j][i]=(1<<30)-1; f[0][0]=0; for (int j=0;j<=t;j++) for (int i=0;i<n;i++){ if (f[j][i]==(1<<30)-1) continue; for (int k=1;k<=m;k++) if (trans[k].a==i && j==trans[k].leave && trans[k].reach<=t+1) f[trans[k].reach][trans[k].b]=min(f[trans[k].reach][trans[k].b],f[j][i]+trans[k].cost); f[j+1][i]=min(f[j+1][i],f[j][i]); } cout<<(f[t+1][n-1]==(1<<30)-1?-1:f[t+1][n-1]);}新闻热点
疑难解答
