結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー ks2mks2m
提出日時 2021-06-11 23:21:06
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 2,707 bytes
コンパイル時間 6,111 ms
コンパイル使用メモリ 79,708 KB
実行使用メモリ 630,460 KB
最終ジャッジ日時 2024-12-15 02:40:05
合計ジャッジ時間 89,903 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 42 WA * 4 TLE * 5 MLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int s = Integer.parseInt(sa[1]) - 1;
int t = Integer.parseInt(sa[2]) - 1;
int k = Integer.parseInt(sa[3]);
sa = br.readLine().split(" ");
int[] x = new int[n];
for (int i = 0; i < n; i++) {
x[i] = Integer.parseInt(sa[i]);
}
List<List<Hen>> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
int m = Integer.parseInt(br.readLine());
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]) - 1;
int b = Integer.parseInt(sa[1]) - 1;
int c = Integer.parseInt(sa[2]);
list.get(a).add(new Hen(b, c));
}
br.close();
long[][] d = new long[k][n];
int[][] pre = new int[k][n];
int[][] pre2 = new int[k][n];
for (int i = 0; i < k; i++) {
Arrays.fill(d[i], Long.MAX_VALUE);
}
d[0][s] = x[s];
PriorityQueue<Node> que = new PriorityQueue<Node>();
Node first = new Node(s, 0, x[s]);
que.add(first);
while (!que.isEmpty()) {
Node cur = que.poll();
if (cur.d > d[cur.v2][cur.v]) {
continue;
}
for (Hen hen : list.get(cur.v)) {
long alt = d[cur.v2][cur.v] + hen.c + x[hen.v];
int nx2 = Math.min(cur.v2 + 1, k - 1);
if (alt < d[nx2][hen.v]) {
d[nx2][hen.v] = alt;
pre[nx2][hen.v] = cur.v;
pre2[nx2][hen.v] = cur.v2;
que.add(new Node(hen.v, nx2, alt));
}
}
}
long ans = d[k - 1][t];
if (ans == Long.MAX_VALUE) {
System.out.println("Impossible");
return;
}
System.out.println("Possible");
System.out.println(ans);
List<Integer> his = new ArrayList<>();
int now = t;
int now2 = k - 1;
his.add(now + 1);
while (now != s || now2 > 0) {
now = pre[now2][now];
now2 = pre2[now2][now];
his.add(now + 1);
}
System.out.println(his.size());
StringBuilder sb = new StringBuilder();
for (int i = his.size() - 1; i >= 0; i--) {
sb.append(his.get(i)).append(' ');
}
sb.deleteCharAt(sb.length() - 1);
System.out.println(sb.toString());
}
static class Hen {
int v, c;
public Hen(int v, int c) {
this.v = v;
this.c = c;
}
}
static class Node implements Comparable<Node> {
int v, v2;
long d;
public Node(int v, int v2, long d) {
this.v = v;
this.v2 = v2;
this.d = d;
}
public int compareTo(Node o) {
return Long.compare(d, o.d);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0