도로 와 항로 (SPFA 알고리즘) (Bellman - ford 알고리즘 최적화)

문 제 는 농부 존 이 새로운 지역 의 우유 배달 계약 에 대해 연구 하고 있다 는 것 이다.그 는 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.
이 문 제 는 언뜻 보기 에는 방향 그림 과 무 방향 그림 이 있 는 혼합 형 이다. 그러나 우 리 는 가장 짧 은 길 에서 정 권 변 에 대해 지나 갈 수 있 는 정 권 변 은 당연히 적 을 수록 좋다 는 것 을 알 수 있다. 그러나 문제 에서 마이너스 가 있 는 변 은 방향 이 있다 고 말 했다. 즉, 한 번 만 지나 갈 수 있다 는 것 이다 (마이너스 링 상황 제외). 이것 은 Bellman - ford 알고리즘 만 사용 할 수 있다.이 알고리즘 은 이전에 말 한 적 이 있 는데 최적화 라 고 하 는데 SPFA 알고리즘 이 라 고 하 는데 이 최적화 에 대해 자세히 설명 하지 않 았 습 니 다. 이번 에는 이 알고리즘 으로 이 문 제 를 해결 하 더 라 도

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main 
{   
    static int INF=100000*100000+1;
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        int R=sc.nextInt();
        int P=sc.nextInt();
        int S=sc.nextInt();//      
        ArrayList list[]=new ArrayList[T+1];//   
        int x,y,w;
        for(int i=0;iif(list[x]==null)list[x]=new ArrayList<>();
            if(list[y]==null)list[y]=new ArrayList<>();
            list[x].add(new Edge(y,w));
            list[y].add(new Edge(x,w));//     
        }
        for(int i=0;i
if(list[x]==null)list[x]=new ArrayList<>();
            list[x].add(new Edge(y,w));//     ，                   
        }
        int d[]=new int[T+1];//  S                   

        boolean inQ[]=new boolean[T+1];//       ，   true
        for(int i=1;i<=T;i++)d[i]=INF;//        
        d[S]=0;//         0
        inQ[S]=true;//        
        Queue queue=new LinkedList<>();
        queue.add(S);

        while(!queue.isEmpty())
        {
            int s=queue.poll();//  
            inQ[s]=false;//  
            if(list[s]==null)continue;//             ，                ArrayList     ，        ，        
            for(int i=0;i<list[s].size();i++)
            {
                Edge e=list[s].get(i);//     s         
                if(d[s]d[s]+e.w)//    
                {
                    d[e.to]=d[s]+e.w;
                    if(!inQ[e.to])//               ，     ，，       
                    {
                        queue.add(e.to);
                        inQ[e.to]=true;
                    }
                }
            }
        }
        for(int i=1;i<=T;i++)
        {
            if(d[i]==INF)//               ，          
                System.out.println("NO PATH");
            else
                System.out.println(d[i]);

        }
    }
}
class Edge//    
{
    int to,w;
    Edge(int to,int w)
    {
        this.to=to;
        this.w=w;
    }
}

이 알고리즘 에 대해 우 리 는 이렇게 이해 할 수 있 습 니 다. 느슨 한 조작 을 거 친 점 을 대열 에 넣 어야 하 는 이 유 는 이 점 의 업데이트 가 후속 점 의 최 단 로 업데이트 에 영향 을 줄 수 있 기 때 문 입 니 다. 모든 점 에 최 단 로 가 존재 하거나 도달 하지 못 한다 고 가정 하면 몇 차례 의 순환 을 거 쳐 느슨 한 조작 은 다시 발생 하지 않 을 것 입 니 다. 따라서...더 이상 입단 할 경 우 는 없 을 것 이 며, 대열 은 결국 비어 있 을 것 이다. 왜냐하면 제목 이 요구 하기 때문에 마이너스 고리 가 없 을 것 이다.만약 에 네 거 티 브 링 이 있다 면 일부 점 의 업데이트 작업 은 계속 진행 되 고 무한 한 작은 추 세 를 보 이 며 순환 이 생 길 것 입 니 다. 대기 열 이 비어 있 지 않 기 때 문 입 니 다. 이런 상황 에 대한 조사 에 있어 서 우 리 는 배열 update [T + 1] 를 설정 하여 한 점 의 업데이트 횟수 를 기록 할 수 있 습 니 다. 예 를 들 어 한 점 의 업데이트 횟수 가 T - 1 회 를 초과 하면 이 그림 에 네 거 티 브 링 이 존재 한 다 는 것 을 설명 합 니 다.이로써 절 차 를 중지 하 다.