結果
| 問題 | No.848 なかよし旅行 |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-07-06 18:29:42 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 556 ms / 2,000 ms |
| コード長 | 9,463 bytes |
| コンパイル時間 | 5,060 ms |
| コンパイル使用メモリ | 82,320 KB |
| 実行使用メモリ | 57,040 KB |
| 最終ジャッジ日時 | 2024-11-08 00:58:21 |
| 合計ジャッジ時間 | 11,863 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder848 {private static Scanner sc;private static Printer pr;private static void solve() {int n = sc.nextInt();int m = sc.nextInt();int p = sc.nextInt() - 1;int q = sc.nextInt() - 1;int t = sc.nextInt();int[][] abc = sc.nextIntArrays(m, 3);Dijkstra di = new Dijkstra(n);for (int i = 0; i < m; i++) {int a = abc[0][i] - 1;int b = abc[1][i] - 1;int c = abc[2][i];di.addEdge(a, b, c);di.addEdge(b, a, c);}di.getShortestPath(0, p);long[] d1 = di.d.clone();di.getShortestPath(p, 0);long[] dp = di.d.clone();di.getShortestPath(q, 0);long[] dq = di.d.clone();long ans = -1;if (d1[p] + dp[q] + d1[q] <= t || d1[q] + dq[p] + d1[p] <= t) {ans = t;} else {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {long t1 = d1[i];long tp1 = dp[i];long tp2 = dp[j];long tq1 = dq[i];long tq2 = dq[j];long t3 = d1[j];long pp = t1 + tp1 + tp2 + t3;long qq = t1 + tq1 + tq2 + t3;if (Math.max(pp, qq) > t) {continue;}ans = Math.max(ans, t1 + t3 + t - Math.max(pp, qq));}}}pr.println(ans);}/*** Dijkstra法による重み付き有向グラフ上の単一始点最短路問題を解く* 重みは非負でなければならない* O(E logV)*/static class Dijkstra {long[] d;List<List<Edge>> edges;private PriorityQueue<Vertex> pq;private int n;private int s;int[] p;final long INF = Long.MAX_VALUE;/*** n個の頂点を持つグラフに関するインスタンスを返す** @param n グラフの頂点数*/Dijkstra(int n) {this.n = n;edges = new ArrayList<>(n);for (int ii = 0; ii < n; ii++) {edges.add(new ArrayList<Edge>());}s = - 1;}/*** グラフに有向辺(頂点 i から頂点 j へ)を追加する* 無向グラフの場合は、逆向きも追加すること** @param i 有向辺の始点(from){@literal (0<=i<n)}* @param j 有向辺の終点(to){@literal (0<=i<n)}* @param c 有向辺の重み({@literal c>=0}でなければならない)*/public void addEdge(int i, int j, int c) {edges.get(i).add(new Edge(i, j, c));}/*** 始点 i から終点 j までの最短路重みを返す* 始点が同じ場合は前回の最短路結果を使い回す* i を以前の呼び出しから変更した場合、最短路を計算しなおす(有向辺の情報はそのままで)** @param i 最短路を求める始点{@literal (0<=i<n)}* @param j 最短路を求める終点{@literal (0<=j<n)}* @return 最短路重み。始点から終点に到達できない場合、INF*/public long getShortestPathWeight(int i, int j) {if (s != i) {s = i;d = new long[n];Arrays.fill(d, INF);d[s] = 0;p = new int[n];Arrays.fill(p, -1);pq = new PriorityQueue<Vertex>();pq.add(new Vertex(s, d[s]));while (!pq.isEmpty()) {Vertex u = pq.poll();if (d[u.me] < u.d) {continue; // skip old vertex}List<Edge> uu = edges.get(u.me);for (Edge v : uu) {if (d[u.me] == INF) {} else if (d[v.v] > d[u.me] + v.w) {d[v.v] = d[u.me] + v.w;pq.add(new Vertex(v.v, d[v.v]));p[v.v] = u.me;} else if (d[v.v] == d[u.me] + v.w) {}}}}return d[j];}/*** 始点 i から終点 j までの最短路のうち1つを返す* 始点が同じ場合は前回の最短路結果を使い回す* i を以前の呼び出しから変更した場合、最短路を計算しなおす(有向辺の情報はそのままで)** @param i 最短路を求める始点{@literal (0<=i<n)}* @param j 最短路を求める終点{@literal (0<=j<n)}* @return 最短路を示す頂点の集合。始点から終点に到達できない場合、null*/public List<Integer> getShortestPath(int i, int j) {if (s != i) {getShortestPathWeight(i, j);}if (d[j] == INF) {return null;}List<Integer> ret = new ArrayList<>();ret.add(j);while (p[j] >= 0) {j = p[j];ret.add(j);}Collections.reverse(ret);return ret;}private static class Edge {// int u; // fromint v; // toint w; // costEdge(int u, int v, int w) {// this.u = u;this.v = v;this.w = w;}}private static class Vertex implements Comparable<Vertex> {int me; // melong d; // costVertex(int u, long w) {this.me = u;this.d = w;}@Overridepublic int compareTo(Vertex o) {return Long.compare(d, o.d);}}}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}static class Scanner {BufferedReader br;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}private boolean isPrintable(int ch) {return ch >= '!' && ch <= '~';}private boolean isCRLF(int ch) {return ch == '\n' || ch == '\r' || ch == -1;}private int nextPrintable() {try {int ch;while (!isPrintable(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}return ch;} catch (IOException e) {throw new NoSuchElementException();}}String next() {try {int ch = nextPrintable();StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (isPrintable(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int nextInt() {try {// parseInt from Integer.parseInt()boolean negative = false;int res = 0;int limit = -Integer.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Integer.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}int multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}long nextLong() {try {// parseLong from Long.parseLong()boolean negative = false;long res = 0;long limit = -Long.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Long.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}long multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}float nextFloat() {return Float.parseFloat(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {try {int ch;while (isCRLF(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (!isCRLF(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int[] nextIntArray(int n) {int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = sc.nextInt();}return ret;}int[][] nextIntArrays(int n, int m) {int[][] ret = new int[m][n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[j][i] = sc.nextInt();}}return ret;}void close() {try {br.close();} catch (IOException e) {// throw new NoSuchElementException();}}}static class Printer extends PrintWriter {Printer(OutputStream out) {super(out);}void printInts(int... a) {StringBuilder sb = new StringBuilder(32);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}void printLongs(long... a) {StringBuilder sb = new StringBuilder(64);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}void printStrings(String... a) {StringBuilder sb = new StringBuilder(32);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}}}