블 루 브리지 컵알고리즘 증가도로 와 항로 (전형 적 인 SPFA 알고리즘 문제)

문 제 는 농부 존 이 새로운 지역 의 우유 배달 계약 에 대해 연구 하고 있다 는 것 이다.그 는 T 개 도시 (표 호 는 1. T) 로 우 유 를 나 눠 줄 계획 이다. 이 도시 들 은 R 개 도시 (1. R) 로 표 시 된 도로 와 P 개 도시 (1. P) 로 표 시 된 항로 가 연결 되 어 있다.모든 도로 i 또는 항로 i 는 도시 와 읍 을 연결 하 는 Ai (1 & lt; A i & gt; = T) 와 Bi (1 & lt; = Bi & gt; = T) 의 대 가 를 Ci 로 표시 한다.모든 도로 에서 Ci 의 범 위 는 0 < = Ci < = 10, 000 이다.이상 한 운영 전략 으로 인해 모든 항로 의 Ci 는 마이너스 일 수 있 습 니 다. 즉, - 10, 000 < = Ci < = 10, 000 입 니 다.모든 도 로 는 양 방향 이 고 정방 향 과 역방향 의 비용 은 똑 같 으 며 모두 마이너스 이다.모든 항 로 는 입력 한 아이 와 비 에 따라 아이 - > 비의 일방 통행 을 한다.실제로 지금 아이 에서 비 로 가 는 항로 가 있다 면 비 에서 아이 로 가 는 통행 방안 이 없 을 것 이라는 뜻 이다.농부 존 은 그의 좋 은 우 유 를 배 송 센터 에서 각 도시 로 보 내 고 싶 어 합 니 다. 물론 대가 가 적 을 수록 좋 기 를 바 랍 니 다. 당신 은 그 를 도와 줄 수 있 습 니까?배 송 센터 는 도시 S 중 (1 & lt; = S & gt; = T) 에 있 습 니 다.
입력 형식 입력 의 첫 줄 에는 빈 칸 으로 구 분 된 네 개의 정수 T, R, P, S 가 포함 되 어 있 습 니 다.그 다음 에 R 행 은 도로 정 보 를 묘사 하고 줄 마다 세 개의 정 수 를 포함 하 며 각각 Ai, Bi 와 Ci 를 나타 낸다.그 다음 에 P 행 은 항로 정 보 를 묘사 하고 줄 마다 세 개의 정 수 를 포함 하 며 각각 Ai, Bi 와 Ci 를 나타 낸다.
출력 형식 출력 T 줄 은 도시 S 에서 도시 마다 최소 비용 을 표시 하고 도착 하지 않 으 면 NO PATH 를 출력 합 니 다.샘플 입력 6, 3, 4, 1, 2, 5, 5, 6, 10, 4, 6 - 100, 1, 3 - 10 샘플 출력 NO PATH NO PATH 5 0 - 95 - 100 데이터 규모 와 약정 에 대한 20% 데이터, T < = 100, R < = 500, P < = 500;30% 의 데이터 에 대해 R < = 1000, R < = 10000, P < = 3000;100% 의 데이터 에 대해 서 는 1 & lt; = T & gt; = 25000, 1 & gt; = R & gt; = 50000, 1 & gt; = P & gt; = 50000.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;

/** * @author   * */
public class Main {
    private static int max=10000000;
    private static int T;//    （      ）
    private static int R;//    （       ）
    private static int P;//    （       ）
    private static int S;//    （    ）
    private static int[] dist;////     1             
    private static Node[] node;//    
    private static ArrayDeque<Integer> queue=new ArrayDeque<Integer>(); 



    /** * @param args */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        spfa();
        print();
    }

    private static void print(){
        for(int i=1;i<=T;i++){
            if(dist[i]<max){
                System.out.println(dist[i]);
            }else{
                System.out.println("NO PATH");
            }
        }
    }

    private static void init(){
        Scanner sc=new Scanner(System.in);
        T=sc.nextInt();
        R=sc.nextInt();
        P=sc.nextInt();
        S=sc.nextInt();
        dist=new int[T+1];
        node=new Node[T+1];

        for(int i=1;i<=T;i++){
            dist[i]=max;
            node[i]=new Node();
        }

        dist[S]=0;
        queue.add(S);

        for(int i=0;i<R;i++){
            int from=sc.nextInt();
            int to=sc.nextInt();
            int weight=sc.nextInt();

            node[from].list.add(to);
            node[from].weight.add(weight);

            node[to].list.add(from);
            node[to].weight.add(weight);
        }

        for(int i=0;i<P;i++){
            int from=sc.nextInt();
            int to=sc.nextInt();
            int weight=sc.nextInt();

            node[from].list.add(to);
            node[from].weight.add(weight);
        }
        sc.close();
    }

    //                    
    //1.   
    //2.    
    //
    //   ： d       INF（   ）；p       s（   ），     -1，           d[s]=0;
    //           ，        0。     ；（                     vis  ，              ）
    //
    //  +    
    //      u，      u  （      ）；   u      v      ，        （  d[v]  ），     ，
    //  ，   v      ，     v  （    ），         ，       
    //    ，                  
    //
    //SPFA       
    //  :         ，  SPFA          。
    //  ：
    //        ，           。   ，           v        d[v]  。
    //         d    。               ，             。
    //  ，          ，  d      ，          ，    ，
    //                      。（  ）
    //        O(ke)，   k            ，    k      2。
    /** private static void spfa(){ while(queue.size()!=0){ //      u，      u  （      ）； //   u      v      ，        （  d[v]  ），     ， //  ，   v      ，     v  （    ），         ，        //    ，                   int queFir=queue.poll(); for(int i=0;i<node[queFir].list.size();i++){ int t=node[queFir].list.get(i); int weight=node[queFir].weight.get(i); if(dist[queFir]+weight<dist[t]){ dist[t]=dist[queFir]+weight; path[t]=queFir; if(!queue.contains(t)){ queue.offer(t); } } } } } */
    private static void spfa(){
        while(queue.size()!=0){
            int queueFir=queue.poll();
            for(int i=0;i<node[queueFir].list.size();i++){
                int v=node[queueFir].list.get(i);
                int weight=node[queueFir].weight.get(i);
                if(dist[queueFir]+weight<dist[v]){
                    dist[v]=dist[queueFir]+weight;
                    if(!queue.contains(v)){
                        queue.offer(v);
                    }
                }
            }
        }
    }
}

class Node{
    ArrayList<Integer> list=new ArrayList<Integer>();
    ArrayList<Integer> weight=new ArrayList<Integer>();
}