結果

問題 No.3111 Toll Optimization
ユーザー vjudge1
提出日時 2025-04-21 21:58:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 231 ms / 5,000 ms
コード長 1,636 bytes
コンパイル時間 2,110 ms
コンパイル使用メモリ 198,436 KB
実行使用メモリ 23,792 KB
最終ジャッジ日時 2025-04-21 21:58:30
合計ジャッジ時間 9,869 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:69:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         scanf("%d%d%d",&n,&m,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:70:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |         for(i=1;i<=m;i++) scanf("%d",&w[i]);
      |                           ~~~~~^~~~~~~~~~~~
main.cpp:74:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |                 scanf("%d%d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const int MAX=1e5+10;
struct Dijkstra
{
	#define type ll
	#define inf LLINF
	struct node
	{
		int id,k;
		type v;
		friend bool operator <(node a,node b){return a.v>b.v;}
	};
	static const int N=MAX;
	vector<node> mp[N];
	type dis[N][12];
	int n,vis[N][5];
	void init(int _n)
	{
		n=_n;
		for(int i=0;i<=n;i++) mp[i].clear();
	}
	void add_edge(int x,int y,type v){mp[x].push_back({y,0,v});}
	void work(int s,int K)
	{
		int i,to;
		type w;
		priority_queue<node> q;
		for(i=0;i<=n;i++)
		{
			memset(dis[i],0x3f,sizeof dis[i]);
			memset(vis[i],0,sizeof vis[i]);
		}
		dis[s][0]=0;
		q.push({s,0,type(0)});
		while(!q.empty())
		{
			node t=q.top();
			q.pop();
			if(vis[t.id][t.k]) continue;
			vis[t.id][t.k]=1;// this node has already been extended
			for(auto &it:mp[t.id])
			{
				to=it.id;
				w=it.v;
				if(dis[to][t.k]>dis[t.id][t.k]+w)
				{
					dis[to][t.k]=dis[t.id][t.k]+w;
					if(!vis[to][t.k]) q.push({to,t.k,dis[to][t.k]}); 
				}
				if(t.k+1<=K && dis[to][t.k+1]>dis[t.id][t.k])
				{
					dis[to][t.k+1]=dis[t.id][t.k];
					if(!vis[to][t.k+1]) q.push({to,t.k+1,dis[to][t.k+1]}); 
				}
			}
		}
	}
	#undef type
	#undef inf
}dij;
int w[MAX];
int main()
{
	int n,m,k,i,a,b,s,t;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++) scanf("%d",&w[i]);
	dij.init(n);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		dij.add_edge(a,b,w[i]);
		dij.add_edge(b,a,w[i]);
	}
	dij.work(1,k);
	ll ans=LLINF;
	for(i=0;i<=k;i++) ans=min(ans,dij.dis[n][i]);
	if(ans==LLINF) ans=-1;
	printf("%lld\n",ans);
}
0