#589388 (C++14) No.1308 ジャンプビーコン

• 問題: No.1308 ジャンプビーコン
• ユーザー: Haa
• 提出日時: 2020-12-05 00:54:57
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,446 ms / 4,000 ms
• コード長: 1,374 bytes
• コンパイル時間: 1,815 ms
• コンパイル使用メモリ: 176,596 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-15 09:34:29
• 合計ジャッジ時間: 41,888 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	4 ms; 5,376 KB
testcase_11	AC	4 ms; 5,376 KB
testcase_12	AC	4 ms; 5,376 KB
testcase_13	AC	123 ms; 5,376 KB
testcase_14	AC	123 ms; 5,376 KB
testcase_15	AC	112 ms; 5,376 KB
testcase_16	AC	112 ms; 5,376 KB
testcase_17	AC	107 ms; 5,376 KB
testcase_18	AC	2,304 ms; 5,376 KB
testcase_19	AC	2,335 ms; 5,376 KB
testcase_20	AC	2,115 ms; 5,376 KB
testcase_21	AC	2,076 ms; 5,376 KB
testcase_22	AC	1,903 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	4 ms; 5,376 KB
testcase_25	AC	3 ms; 5,376 KB
testcase_26	AC	2,441 ms; 5,376 KB
testcase_27	AC	2,412 ms; 5,376 KB
testcase_28	AC	2,421 ms; 5,376 KB
testcase_29	AC	1,316 ms; 5,376 KB
testcase_30	AC	1,271 ms; 5,376 KB
testcase_31	AC	1,099 ms; 5,376 KB
testcase_32	AC	1,301 ms; 5,376 KB
testcase_33	AC	1,405 ms; 5,376 KB
testcase_34	AC	2,445 ms; 5,376 KB
testcase_35	AC	2,446 ms; 5,376 KB
testcase_36	AC	2,156 ms; 5,376 KB
testcase_37	AC	2,162 ms; 5,376 KB
testcase_38	AC	2,323 ms; 5,376 KB
testcase_39	AC	2,292 ms; 5,376 KB

コンパイルメッセージ

main.cpp: In function 'void dijkstra(int, bool)':
main.cpp:50:55: warning: narrowing conversion of 'e.edge::to' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   50 |                                 que.push(qu{d[e.to],e.to});
      |                                                     ~~^~

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(v) v.begin(),v.end()
constexpr ll MOD=998244353;
constexpr ll INF=1e18;

struct edge { 
	ll to, cost; 
};
struct qu {
	ll d; int v;
	bool operator<(const qu &another) const {return d > another.d;};
};
int n, q, c;
vector<edge> G[4000];
vector<ll> d(4000, INF);
vector<ll> bd(4000, INF);

void dijkstra(int s, bool f){
	priority_queue<qu> que;
	if(f){
		REP(i,n){
			que.push(qu{bd[i]+c,i});
			d[i]=bd[i]+c;
		}
		que.push(qu{bd[n],s});
		d[s]=bd[n];
	}
	else{
		REP(i,n){
			d[i]=INF;
		}
		que.push(qu{0,s});
		d[s]=0;
	}
	while(!que.empty()){
		qu p=que.top();
		que.pop();
		int v=p.v;
		if(d[v]<p.d) continue;
		REP(i,G[v].size()){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push(qu{d[e.to],e.to});
			}
		}
	}
}

int main(){
	cin >> n >> q >> c;
	int u, v, l;
	REP(i,n-1){
		cin >> u >> v >> l;
		u--, v--;
		G[u].push_back({v,l});
		G[v].push_back({u,l});
	}
	int x, pre;
	cin >> pre; pre--;
	vector<ll> bdt(n,0);
	bd[n]=0;
	REP(i,q-1){
		cin >> x; x--;
		dijkstra(pre,1);
		REP(i,n) bdt[i]=d[i];
		ll bdn=d[x];
		dijkstra(x,0);
		REP(i,n) bd[i]=min(bd[i]+d[pre],bdt[i]+d[i]);
		bd[n]=bdn;
		pre=x;
	}
	cout << bd[n] << endl;
	return 0;
}