第一眼看过去感觉又是什么魔改BFS的样子,但是感觉不好弄
但是往dp上想就很容易
\(f[i]\)表示走到i的最小代价,按着给出的序列顺序转移即可,转移是O(1)的。
代码非常简单
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++) //
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
ll a[N],b[N],c[N],n,m,k,f[N],id;
ll x,y,z;
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld %lld %lld",&n,&m,&k);
fo(i,1,m){
scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
}
fo(i,1,n) f[i]=inf;
f[1]=0;
fo(i,1,k) {
scanf("%lld",&id);
x=a[id]; y=b[id]; z=c[id];
f[y]=min(f[y], f[x]+z);
}
if (f[n]==inf) puts("-1");
else printf("%lld",f[n]);
return 0;
}