結果

問題 No.788 トラックの移動
コンテスト
ユーザー vjudge1
提出日時 2026-01-25 12:45:35
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 252 ms / 2,000 ms
コード長 1,403 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,991 ms
コンパイル使用メモリ 192,412 KB
実行使用メモリ 12,024 KB
最終ジャッジ日時 2026-01-25 12:45:40
合計ジャッジ時間 4,387 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
const int INF=0x3f3f3f3f3f3f3f3f;
int n,m,l;
int t[N];
int ddis[N];
vector<pair<int,int> >G[N];
struct Node{
	int u,dis;
	Node(int u,int dis):u(u),dis(dis){};
	friend bool operator < (Node a,Node b){
		return a.dis>b.dis;
	}
};
int dis[N],vis[N];
void Dijkstra(int s){
	for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
	priority_queue<Node>q;
	dis[s]=0;
	q.push(Node(s,dis[s]));
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto E:G[u]){
			int v=E.first,w=E.second;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(Node(v,dis[v]));
			}
		}
	}
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>l;
	for(int i=1;i<=n;i++)cin>>t[i];
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back(make_pair(v,w));
		G[v].push_back(make_pair(u,w));
	}
	Dijkstra(l);
	for(int i=1;i<=n;i++)ddis[i]=dis[i];
	int cnt=0;
	for(int i=1;i<=n;i++)cnt+=(t[i]>0);
	if(cnt==1){
		cout<<"0\n";
		return 0;
	}
	int ans=INF;
	for(int i=1;i<=n;i++){
		Dijkstra(i);
		int s=0;
		if(t[l]){
			for(int j=1;j<=n;j++)s+=dis[j]*t[j]*2;
			s-=dis[l];
			ans=min(ans,s);
		}
		else{
			for(int j=1;j<=n;j++)s+=dis[j]*t[j]*2;
			for(int j=1;j<=n;j++){
				if(!t[j])continue;
				ans=min(ans,s-dis[j]+ddis[j]);
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}
0