結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー |
![]() |
提出日時 | 2021-06-11 23:01:02 |
言語 | Java (openjdk 23) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,739 bytes |
コンパイル時間 | 3,002 ms |
コンパイル使用メモリ | 82,852 KB |
実行使用メモリ | 895,072 KB |
最終ジャッジ日時 | 2024-12-15 01:53:58 |
合計ジャッジ時間 | 57,001 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 TLE * 3 MLE * 20 |
ソースコード
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();int nk = n + k + 5;long[][] d = new long[n][nk];int[][] pre = new int[n][nk];for (int i = 0; i < n; i++) {Arrays.fill(d[i], Long.MAX_VALUE);}d[s][0] = 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.v][cur.v2]) {continue;}for (Hen hen : list.get(cur.v)) {long alt = d[cur.v][cur.v2] + hen.c + x[hen.v];int nx2 = cur.v2 + 1;if (nx2 < nk && alt < d[hen.v][nx2]) {d[hen.v][nx2] = alt;pre[hen.v][nx2] = cur.v;que.add(new Node(hen.v, nx2, alt));}}}long ans = Long.MAX_VALUE;int ak = 0;for (int i = k - 1; i < d[t].length; i++) {if (d[t][i] < ans) {ans = d[t][i];ak = i;}}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;his.add(now + 1);for (int i = ak; i > 0; i--) {now = pre[now][i];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);}}}