結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー tails
提出日時 2023-03-09 15:15:47
言語 cLay
(20241019-1)
結果
AC  
実行時間 62 ms / 3,000 ms
コード長 612 bytes
コンパイル時間 2,922 ms
コンパイル使用メモリ 180,300 KB
実行使用メモリ 32,512 KB
最終ジャッジ日時 2024-09-18 02:53:48
合計ジャッジ時間 12,489 ms
ジャッジサーバーID
(参考情報)
judge6 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 67
権限があれば一括ダウンロードができます

ソースコード

diff #

ll@n,@s--,@t--,@k,@x[n],@m;
int y[m],a[],b[],c[n*k];
rd((a--,b--,y)(m));
wgraph<int>g;
g.setDirectEdge(n,m,b,a,y);
DijkstraHeap<ll>h;
h.malloc(n*k,1);
h.change(t*k+(k-1),x[t]);
c[t*k+(k-1)]=-1;
while(h.size){
	int i=h.pop();
	int j=i/k;
	int l=i%k;
	rep(o,g.es[j]){
		int p=g.edge[j][o];
		int r=max(0,l-1);
		int q=p*k+r;
		ll v=h.val[i]+g.cost[j][o]+x[p];
		if(!h.visited[q]&&(h.place[q]<0||h.val[q]>v)){
			h.change(q,v);
			c[q]=i;
		}
	}
}
if(h.visited[s*k]){
	wt("Possible");
	wt(h.val[s*k]);
	int z[n*k],w=0,u=s*k;
	while(u>=0){
		z[w++]=u/k+1;
		u=c[u];
	}
	wt(w);
	wt(z(w));
}else{
	wt("Impossible");
}
0