#1#6 未过,求调,玄关
查看原帖
#1#6 未过,求调,玄关
1302823
sto_DFS_orz楼主2024/8/10 09:40
#include<bits/stdc++.h>
#define ll long long
#define N 2010
using namespace std;
ll n,m,b,e,k,g,now,u,v,w,tmp;
ll edge[N][N],TT[N][N],last[N];
ll dis[N],vis[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
inline ll read(){
	ll f=1,s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=(s<<3)+(s<<1)+ch-48;
		ch=getchar();
	}
	return f*s;
}
ll check(ll x,ll y){
	if(dis[x]>=TT[x][y]&&dis[x]<=TT[x][y]+edge[x][y]-1)
		return TT[x][y]+edge[x][y]*2;
	return dis[x]+edge[x][y];
}
void dijstra(){
	memset(dis,0x3f,sizeof dis);
	dis[b]=k;
	q.push(make_pair(k,b));
	while(q.size()){
		q.pop();
		v=q.top().second;
		if(vis[v]) continue;
		vis[v]=1;
		for(ll i=1;i<=n;i++){
			if(edge[v][i]){
				tmp=check(v,i);
				if(tmp<dis[i]){
					dis[i]=tmp;
					q.push(make_pair(tmp,i));
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	cin>>b>>e>>k>>g;
	for(ll i=1;i<=g;i++)
		cin>>last[i];
	for(ll i=1;i<=m;i++){
		cin>>u>>v>>w;
		edge[u][v]=w;
		edge[v][u]=w;
	}
	for(ll i=1;i<g;i++){
		TT[last[i]][last[i+1]]=now;
		TT[last[i+1]][last[i]]=now;
		now+=edge[last[i]][last[i+1]];
	}
	dijstra();
	cout<<dis[e]-k;
	return 0;
}
2024/8/10 09:40
加载中...