結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー ks2mks2m
提出日時 2021-06-11 23:04:21
言語 Java
(openjdk 23)
結果
RE  
実行時間 -
コード長 2,787 bytes
コンパイル時間 3,145 ms
コンパイル使用メモリ 79,792 KB
実行使用メモリ 67,580 KB
最終ジャッジ日時 2024-12-15 02:01:21
合計ジャッジ時間 30,228 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 45 RE * 22
権限があれば一括ダウンロードができます

ソースコード

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();
if (n > 1000) {
throw new Exception();
}
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);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0