HDU 1874 원활 한 공사 계속

원활 한 공사 가 계속되다.
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19989 Accepted Submission(s): 6912
Problem Description
모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다.한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 선택 할 수 있 고 어떤 방안 은 다른 방안 보다 걷 는 거리 가 훨씬 짧다.이것 은 행인 들 을 매우 곤란 하 게 한다.
지금 은 출발점 과 종점 을 알 고 있 습 니 다.출발점 에서 종점 까지 가장 짧 은 거 리 를 걸 어야 하 는 지 계산 해 보 세 요.

Input
이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다.파일 이 끝 날 때 까지 처리 하 십시오.
각 조 의 데이터 첫 줄 은 두 개의 정수 N 과 M(0다음은 M 행 도로 정보.각 줄 마다 세 개의 정수 A,B,X(0<=A,B다음 줄 에 두 개의 정수 S,T(0<=S,T

Output
각 그룹의 데 이 터 는 한 줄 에서 가장 짧 은 걸 어야 할 거 리 를 출력 하 십시오.S 에서 T 까지 의 노선 이 존재 하지 않 으 면 출력-1.

Sample Input
3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2

Sample Output
2 -1

사고방식:Dijistra 알고리즘 을 사용 하여 최 단 경 로 를 구하 다
요약: Dijistra 알고리즘 을 사용 하여 최 단 경 로 를 구하 십시오. 가장 짧 은 경 로 를 구 하려 면 우 리 는 처음부터 모든 점 까지 의 거 리 를 계산 해 야 한다.그 중에서 가장 짧 은 것 을 취해 야 한다.나 는 처음부터 종점 까지 의 거 리 를 계산 하기 시작 했다.결 과 는 WA 가 여러 번 있 었 고 나중에 야 발견 했다.

import java.io.*;
import java.util.*;
public class Main {
	public static int M=202;
	public static int MAX=2000000;
	public static int map[][]=new int[M][M];
	public static ArrayList<Integer> ay;
	public static int n,m,s,t;
	public static void main(String[] args) {
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		while(sc.hasNextInt()){
			ay=new ArrayList<Integer>();//                
			//      
			for(int i=0;i<M;i++){
				for(int j=0;j<M;j++){
					map[i][j]=MAX;
				}
			}
			
			n=sc.nextInt();
			m=sc.nextInt();
			
			for(int i=0;i<m;i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				int x=sc.nextInt();
				//       ，    ，      
				if(map[a][b]>x){
					map[a][b]=map[b][a]=x;//      ，             
				}
			}
			s=sc.nextInt();
			t=sc.nextInt();
			getDistance(s);
			if(ay.get(t)<MAX)//        ，      ，     
				System.out.println(ay.get(t));
			else 
				System.out.println("-1");
		}
	}
	public static void getDistance(int v){
		boolean boo[]=new boolean[M];//           
		int k=0;
		for(int i=0;i<=n;i++){
			ay.add(map[v][i]);//                
		}
		boo[v]=true;
		ay.set(v,0);
		for(int i=0;i<=n;i++){
			int min=MAX;
			//              ，     。
			for(int j=0;j<=n;j++){
				if(!boo[j]&&ay.get(j)<min){
					min=ay.get(j);
					k=j;
				}
			}
			boo[k]=true;
			if(min==MAX) break;
			//         ，               
			for(int j=0;j<=n;j++){
				if(!boo[j]&&ay.get(j)>ay.get(k)+map[k][j]){
					ay.set(j,ay.get(k)+map[k][j]);
				}
			}
		}
	}
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU] 4089 활성화 확률 DP

dp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 1874 원활 한 공사 계속

좋은 웹페이지 즐겨찾기