結果
| 問題 | No.807 umg tours |
| ユーザー |
 kitakitalily
|
| 提出日時 | 2019-03-23 12:43:39 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,466 bytes |
| コンパイル時間 | 5,023 ms |
| コンパイル使用メモリ | 82,264 KB |
| 実行使用メモリ | 169,524 KB |
| 最終ジャッジ日時 | 2023-10-22 03:41:21 |
| 合計ジャッジ時間 | 40,597 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge9 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 217 ms
54,772 KB |
| testcase_01 | AC | 223 ms
55,140 KB |
| testcase_02 | AC | 237 ms
60,376 KB |
| testcase_03 | AC | 232 ms
59,928 KB |
| testcase_04 | AC | 212 ms
54,884 KB |
| testcase_05 | AC | 219 ms
55,880 KB |
| testcase_06 | AC | 236 ms
60,452 KB |
| testcase_07 | AC | 228 ms
60,120 KB |
| testcase_08 | AC | 160 ms
53,704 KB |
| testcase_09 | AC | 177 ms
54,004 KB |
| testcase_10 | AC | 195 ms
54,208 KB |
| testcase_11 | AC | 2,273 ms
135,284 KB |
| testcase_12 | AC | 2,097 ms
133,520 KB |
| testcase_13 | AC | 2,303 ms
145,548 KB |
| testcase_14 | AC | 1,568 ms
117,540 KB |
| testcase_15 | AC | 1,419 ms
114,544 KB |
| testcase_16 | AC | 2,490 ms
147,584 KB |
| testcase_17 | AC | 2,834 ms
169,056 KB |
| testcase_18 | AC | 2,741 ms
168,344 KB |
| testcase_19 | AC | 2,769 ms
169,524 KB |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | AC | 2,222 ms
153,108 KB |
| testcase_25 | AC | 2,747 ms
167,968 KB |
ソースコード
import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Map;
import java.util.HashMap;
import java.util.TreeSet;
import java.util.Comparator;
public class Main {
static int mod = 1000000007;
static int size = 510000;
static long[] fac = new long[size];
static long[] finv = new long[size];
static long[] inv = new long[size];
static int INF = Integer.MAX_VALUE;
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] a = new int[m];
int[] b = new int[m];
int[] c = new int[m];
ArrayList<Edge>[] edges = new ArrayList[2*n];
for(int i = 0; i < 2 * n; i++){
edges[i] = new ArrayList<Edge>();
}
for(int i = 0; i < m; i++){
a[i] = scanner.nextInt()-1;
b[i] = scanner.nextInt()-1;
c[i] = scanner.nextInt();
edges[a[i]].add(new Edge(b[i], c[i]));
edges[b[i]].add(new Edge(a[i], c[i]));
edges[a[i]+n].add(new Edge(b[i]+n, c[i]));
edges[b[i]+n].add(new Edge(a[i]+n, c[i]));
edges[a[i]].add(new Edge(b[i]+n, 0));
edges[b[i]].add(new Edge(a[i]+n, 0));
}
int[] dist = dijkstra(2 * n, edges, 0);
System.out.println(0);
for(int i = 1; i < n; i++){
System.out.println(dist[i] + dist[n+i]);
}
}
public static int[] dijkstra(int n, ArrayList<Edge>[] edges,int start){
boolean[] visited = new boolean[n];
int[] distance = new int[n];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;
Queue<Edge> que = new PriorityQueue<Edge>();
que.add(new Edge(start, 0));
while(!que.isEmpty()){
Edge e = que.poll();
if(visited[e.to]){
continue;
}
visited[e.to] = true;
for(Edge next : edges[e.to]){
if(!visited[next.to]){
if(distance[next.to] > distance[e.to] + next.cost){
distance[next.to] = distance[e.to] + next.cost;
que.add(new Edge(next.to, distance[next.to]));
}
}
}
}
return distance;
}
static class Edge implements Comparable<Edge>{
int to;
int cost;
Edge(int to,int cost){
this.to = to;
this.cost = cost;
}
public int compareTo(Edge e) {
return this.cost - e.cost;
}
}
//繰り返し二乗法
public static long pow(long x, long n){
long ans = 1;
while(n > 0){
if((n & 1) == 1){
ans = ans * x;
ans %= mod;
}
x = x * x % mod;
n >>= 1;
}
return ans;
}
//fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要
public static void initComb(){
fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1;
for (int i = 2; i < size; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
}
//nCk % mod
public static long comb(int n, int k){
return fac[n] * finv[k] % mod * finv[n - k] % mod;
}
//n! % mod
public static long fact(int n){
return fac[n];
}
//(n!)^-1 with % mod
public static long finv(int n){
return finv[n];
}
static class Pair implements Comparable<Pair>{
int x, y;
Pair(int a, int b){
x = a;
y = b;
}
@Override
public boolean equals(Object o){
if (this == o) return true;
if (!(o instanceof Pair)) return false;
Pair p = (Pair) o;
return x == p.x && y == p.y;
}
@Override
public int compareTo(Pair p){
//return x == p.x ? y - p.y : x - p.x; //xで昇順にソート
//return (x == p.x ? y - p.y : x - p.x) * -1; //xで降順にソート
//return y == p.y ? x - p.x : y - p.y;//yで昇順にソート
return (y == p.y ? x - p.x : y - p.y)*-1;//yで降順にソート
}
}
static class UnionFind {
int[] parent;
public UnionFind(int size) {
parent = new int[size];
Arrays.fill(parent, -1);
}
public boolean unite(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (parent[y] < parent[x]) {
int tmp = y;
y = x;
x = tmp;
}
parent[x] += parent[y];
parent[y] = x;
return true;
}
return false;
}
public boolean same(int x, int y) {
return root(x) == root(y);
}
public int root(int x) {
return parent[x] < 0 ? x : (parent[x] = root(parent[x]));
}
public int size(int x) {
return -parent[root(x)];
}
}
public static int upperBound(long[] a,long val){
return upperBound(a,0,a.length,val);
}
public static int upperBound(long[] a,int l,int r,long val){
if(r-l==1){
if(a[l]>val) return l;
return r;
}
int mid=(l+r)/2;
if(a[mid]>val){
return upperBound(a,l,mid,val);
}else{
return upperBound(a,mid,r,val);
}
}
public static int lowerBound(long[] a,long val){
return lowerBound(a,0,a.length,val);
}
public static int lowerBound(long[] a,int l,int r,long val){
if(r-l==1){
if(a[l]<val) return r;
return l;
}
int mid=(l+r)/2;
if(a[mid]<val){
return lowerBound(a,mid,r,val);
}else{
return lowerBound(a,l,mid,val);
}
}
}