HDU 1874 원활 한 공정 계속 (Bellman ford 알고리즘)

원활 한 공사 가 계속되다.
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 68677    Accepted Submission(s): 26534  
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
Author
linle
Source
2008 절 대 대학원 재시험 평가 전 (2) - 전진 시 뮬 레이 션
문제 링크: HDU 1874 원활 한 공사 계속
문제 분석: 이 문 제 는 Dijkstra 알고리즘 으로 풀이 하기에 더욱 적합 하 며, Bellman - ford 알고리즘 을 사용 하여 연습 만 을 위 한 것 입 니 다.
프로그램 설명: 약
AC 의 C + + 프로그램:

#include

using namespace std;

const int INF=0x3f3f3f3f;
const int M=1005;

struct Edge{//    
	int start,end,cost;//start end   cost   
}edge[M];

int dist[205];//     
 
bool Bellman_ford(int n,int m)//n   ，m   
{
	for(int i=1;idist[edge[j].start]+edge[j].cost)
		  dist[edge[j].end]=dist[edge[j].start]+edge[j].cost;
	bool flag=true;
	for(int i=0;idist[edge[i].start]+edge[i].cost){
	  	flag=false;
	  	break;
	  }
	return flag;	
}

int main()
{
	int n,m,a,b,x,s,t;
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i=0;i<2*m;i++){
			scanf("%d%d%d",&a,&b,&x);
			edge[i].start=a,edge[i].end=b,edge[i].cost=x;
			i++;
			edge[i].start=b,edge[i].end=a,edge[i].cost=x;
		}
		scanf("%d%d",&s,&t);
		//   
		for(int i=0;i