結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー okkuukenken
提出日時 2025-04-20 11:54:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 319 ms / 5,000 ms
コード長 1,194 bytes
コンパイル時間 6,930 ms
コンパイル使用メモリ 355,716 KB
実行使用メモリ 36,560 KB
最終ジャッジ日時 2025-04-20 11:54:53
合計ジャッジ時間 18,296 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder; 
using ll=long long;
using mint=modint998244353;
const ll inf=(1e9+7)*(1e9+7);
int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0};
const int mod=998244353;
using P=pair<ll,int>;
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	vector<int>c(m),u(m),v(m);
	for(int i=0;i<m;i++)
		cin>>c[i];
	for(int i=0;i<m;i++){
		cin>>u[i]>>v[i];
		u[i]--,v[i]--;
	}
	struct edge{
		int to,cost;
	};
	vector<vector<edge>>G(n*(k+1));
	for(int i=0;i<=k;i++){
		for(int j=0;j<m;j++){
			G[n*i+u[j]].push_back({n*i+v[j],c[j]});
			G[n*i+v[j]].push_back({n*i+u[j],c[j]});
			if(i!=k){
				G[n*i+u[j]].push_back({n*(i+1)+v[j],0});
				G[n*i+v[j]].push_back({n*(i+1)+u[j],0});
			}
		}
	}
	vector<ll>dist(n*(k+1),inf);
	dist[0]=0;
	priority_queue<P,vector<P>,greater<>>que;
	que.push({0,0});
	while(que.size()){
		auto[d,v]=que.top();
		que.pop();
		if(dist[v]<d)
			continue;
		for(auto[u,c]:G[v]){
			if(dist[u]>d+c){
				dist[u]=d+c;
				que.push({d+c,u});
			}
		}
	}
	ll ans=inf;
	for(int i=0;i<=k;i++)
		ans=min(ans,dist[n*i+(n-1)]);
	if(ans==inf)
		ans=-1;
	cout<<ans<<endl;
}
0