結果
| 問題 |
No.1301 Strange Graph Shortest Path
|
| コンテスト | |
| ユーザー |
 watarimaycry2
|
| 提出日時 | 2020-11-27 22:49:20 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,620 bytes |
| コンパイル時間 | 2,449 ms |
| コンパイル使用メモリ | 83,284 KB |
| 実行使用メモリ | 114,156 KB |
| 最終ジャッジ日時 | 2024-07-26 20:05:16 |
| 合計ジャッジ時間 | 34,767 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 WA * 5 |
ソースコード
import java.util.*; import java.io.*; import java.math.*;
public class Main{
static void solve(){//Here is the main function
int N = nextInt();
int M = nextInt();
Node[] list = new Node[N];
Edge[] E = new Edge[M];
for(int i = 0; i < N; i++){
list[i] = new Node(i);
}
for(int i = 0; i < M; i++){
int u = nextInt() - 1;
int v = nextInt() - 1;
int c = nextInt();
int d = nextInt();
list[u].child.add(new Edge(i, v, c, d));
list[v].child.add(new Edge(i, u, c, d));
}
PriorityQueue<Q> pq = new PriorityQueue<>();
HashSet<Integer> usedEdge = new HashSet<>();
pq.add(new Q(0, 0l, -1, -1));
while(pq.size() > 0){
Q now = pq.poll();
int index = now.index;
long cost = now.cost;
int fromEdge = now.fromEdge;
int fromNode = now.fromNode;
if(list[index].firstCost != -1 && list[index].firstCost <= cost){
continue;
}
list[index].firstCost = cost;
list[index].lastEdge = fromEdge;
list[index].lastNode = fromNode;
ArrayList<Edge> child = list[index].child;
for(int i = 0; i < child.size(); i++){
Edge c = child.get(i);
if(list[c.to].firstCost == -1){
pq.add(new Q(c.to, cost + c.C, c.no, index));
}else if(list[c.to].firstCost > cost + c.C){
pq.add(new Q(c.to, cost + c.C, c.no, index));
}
}
}
int lastNode = N - 1;
while(true){
if(lastNode != -1){
usedEdge.add(list[lastNode].lastEdge);
lastNode = list[lastNode].lastNode;
}else{
break;
}
}
myerr(list[N - 1].firstCost);
pq.add(new Q(N - 1, 0l, -1, -1));
while(pq.size() > 0){
Q now = pq.poll();
int index = now.index;
long cost = now.cost;
if(list[index].secondCost != -1 && list[index].secondCost <= cost){
continue;
}
list[index].secondCost = cost;
ArrayList<Edge> child = list[index].child;
for(int i = 0; i < child.size(); i++){
Edge c = child.get(i);
if(usedEdge.contains(c.no)){
c.C = c.D;
}
if(list[c.to].secondCost == -1){
pq.add(new Q(c.to, cost + c.C, c.no, -1));
}else if(list[c.to].secondCost > cost + c.C){
pq.add(new Q(c.to, cost + c.C, c.no, -1));
}
}
}
myerr(list[0].secondCost);
myout(list[0].secondCost + list[N - 1].firstCost);
}
//Method addition frame start
static class Q implements Comparable<Q>{
int index;
long cost;
int fromEdge;
int fromNode;
Q(int index, long cost, int fromEdge, int fromNode){
this.index = index;
this.cost = cost;
this.fromEdge = fromEdge;
this.fromNode = fromNode;
}
public int compareTo(Q ato){
return Long.compare(this.cost, ato.cost);
}
}
static class Edge{
int no;
int to;
int C;
int D;
Edge(int no, int to, int C, int D){
this.no = no;
this.to = to;
this.C = C;
this.D = D;
}
}
static class Node{
int no;
int lastEdge = -1;
int lastNode = -1;
long firstCost = -1;
long secondCost = -1;
ArrayList<Edge> child = new ArrayList<>();
Node(int no){
this.no = no;
}
}
//Method addition frame end
//Don't have to see. start------------------------------------------
static class InputIterator{
ArrayList<String> inputLine = new ArrayList<>(1024);
int index = 0; int max; String read;
InputIterator(){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try{
while((read = br.readLine()) != null){
inputLine.addAll(Arrays.asList(read.split(" ")));
}
}catch(IOException e){}
max = inputLine.size();
}
boolean hasNext(){return (index < max);}
String next(){
if(hasNext()){
return inputLine.get(index++);
}else{
throw new IndexOutOfBoundsException("There is no more input");
}
}
}
static HashMap<Integer, String> CONVSTR = new HashMap<>();
static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
static PrintWriter out = new PrintWriter(System.out);
static void flush(){out.flush();}
static void myout(Object t){out.println(t);}
static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
static String next(){return ii.next();}
static boolean hasNext(){return ii.hasNext();}
static int nextInt(){return Integer.parseInt(next());}
static long nextLong(){return Long.parseLong(next());}
static double nextDouble(){return Double.parseDouble(next());}
static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
static ArrayList<String> nextStrArray(int size){
ArrayList<String> ret = new ArrayList<>(size);
for(int i = 0; i < size; i++){
ret.add(next());
}
return ret;
}
static ArrayList<Integer> nextIntArray(int size){
ArrayList<Integer> ret = new ArrayList<>(size);
for(int i = 0; i < size; i++){
ret.add(Integer.parseInt(next()));
}
return ret;
}
static ArrayList<Long> nextLongArray(int size){
ArrayList<Long> ret = new ArrayList<>(size);
for(int i = 0; i < size; i++){
ret.add(Long.parseLong(next()));
}
return ret;
}
@SuppressWarnings("unchecked")
static String myconv(Object list, int no){//only join
String joinString = CONVSTR.get(no);
if(list instanceof String[]){
return String.join(joinString, (String[])list);
}else if(list instanceof ArrayList){
return String.join(joinString, (ArrayList)list);
}else{
throw new ClassCastException("Don't join");
}
}
static ArrayList<String> myconv(String str, int no){//only split
String splitString = CONVSTR.get(no);
return new ArrayList<String>(Arrays.asList(str.split(splitString)));
}
public static void main(String[] args){
CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
solve();flush();
}
//Don't have to see. end------------------------------------------
}