hduoj - 1874 원활 한 공사 계속 (Dijistra + Floyd + Bellman Ford + SPFA)

원활 한 공사 가 계속되다.
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 23439    Accepted Submission(s): 8253
Problem Description
모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 선택 할 수 있 고 어떤 방안 은 다른 방안 보다 걷 는 거리 가 훨씬 짧다.이것 은 행인 들 을 매우 곤란 하 게 한다.
지금 은 출발점 과 종점 을 알 고 있 습 니 다. 출발점 에서 종점 까지 가장 짧 은 거 리 를 걸 어야 하 는 지 계산 해 보 세 요.
 
Input
이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.
각 조 의 데이터 첫 줄 은 두 개의 정수 N 과 M (0 < N < 200, 0 < M < 1000) 을 포함 하고 각각 기 존 도시 의 수량 과 이미 건 설 된 도로 의 수량 을 대표 한다.도 시 는 각각 0 ～ N - 1 번호 로 되 어 있다.
다음은 M 행 도로 정보.한 줄 에 세 개의 정수 A, B, X (0 < = A, B < N, A! = B, 0 < X < 10000) 가 있 는데 도시 A 와 도시 B 사이 에 X 의 양 방향 도로 가 있다 는 것 을 나타 낸다.
다음 줄 에 두 개의 정수 S, T (0 < = S, T < N) 가 있 는데 각각 출발점 과 종점 을 대표 한다.
 
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 (15ms):

#include <stdio.h>
#include <string.h>
#include <vector>
#define N 220

using namespace std;

struct Road{
	int next;
	int dis;
};

vector<Road>City[N];
int CityNum, RoadNum;
int dij[N];
bool vis[N];

void Init(){
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i <= CityNum; i ++){
		City[i].clear();
		dij[i] = 0xfffffff;
	}
}
void Dijistra(int cur){
	dij[cur] = 0;
	while(vis[cur] == 0){
		vis[cur] = 1;
		for(int i = 0; i < City[cur].size(); i ++){
			int next = City[cur].at(i).next;
			int dis = City[cur].at(i).dis;
			if(dij[next] > dij[cur] + dis){
				dij[next] = dij[cur] + dis;
			}
		}
		int min = 0xfffffff;
		for(int i = 0; i < CityNum; i ++){
			if(!vis[i] && min > dij[i]){
				min = dij[i];
				cur = i;
			}
		}
	}
}

int main()
{
	Road nw;
	while(scanf("%d%d", &CityNum, &RoadNum) != EOF){
		Init();
		int start, end, distance;
		for(int i = 0; i < RoadNum; i ++){
			scanf("%d%d%d", &start, &end, &distance);
			nw.next = start;
			nw.dis = distance;
			City[end].push_back(nw);
			nw.next = end;
			City[start].push_back(nw);			
		}
		scanf("%d%d", &start, &end);
		
		Dijistra(start);
		
		if(dij[end] == 0xfffffff){
			printf("-1
");
		}
		else{
			printf("%d
", dij[end]);
		}
	}
	
	return 0;
}

Floyd (78ms):

#include <stdio.h>
#include <algorithm>
#define N 205

using namespace std;

int map[N][N];
int CityNum, RoadNum;

int floyd(int start, int end){
    for(int k = 0; k < CityNum; k ++){
        for(int i = 0; i < CityNum; i ++){
            for(int j = 0; j < CityNum; j ++){
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    
    return map[start][end] < 0xfffffff ? map[start][end] : -1;
}

int main()
{
    int start, end, len;
    while(scanf("%d%d", &CityNum, &RoadNum) != EOF){
        for(int i = 0; i < CityNum; i ++){
            for(int j = 0; j < CityNum; j ++){
                map[i][j] = (i == j ? 0 : 0xfffffff);
            }
        }
            
        for(int i = 0; i < RoadNum; i ++){
            scanf("%d%d%d", &start, &end, &len);
            if(len < map[start][end]){				//                
				map[end][start] = map[start][end] = len;		//     
			}
        }
        scanf("%d%d", &start, &end);
        
        int ans = floyd(start, end);
        
        printf("%d
", ans);
    }
    
    return 0;
}

Bellman_Ford(15ms):

#include <stdio.h>

struct ROAD{
	int from;
	int to;
	int len;
};

ROAD Road[2020];
int CityNum, RoadNum;
int dis[220];

void Bellman_Ford(int start){
	for(int i = 0; i < CityNum; i ++){
		dis[i] = 0xfffffff;
	}
	dis[start] = 0;
	for(int i = 0; i < CityNum; i ++){
		for(int j = 0; j < RoadNum * 2; j ++){
			if(dis[Road[j].to] > dis[Road[j].from] + Road[j].len){
				dis[Road[j].to] = dis[Road[j].from] + Road[j].len;
			}
		}
	}
}

int main()
{
	int start, end;
	while(scanf("%d%d", &CityNum, &RoadNum) != EOF){
		for(int i = 0; i < RoadNum; i ++){
			scanf("%d%d%d", &Road[i].from, &Road[i].to, &Road[i].len);
			Road[RoadNum + i].from = Road[i].to;
			Road[RoadNum + i].to = Road[i].from;
			Road[RoadNum + i].len = Road[i].len;
		}
		scanf("%d%d", &start, &end);
		
		Bellman_Ford(start);
		
		if(dis[end] == 0xfffffff){
			printf("-1
");
		}
		else{
			printf("%d
", dis[end]);
		}
	}
	
	return 0;
}

SPFA (0ms):

#include <stdio.h>
#include <string.h>
#include <queue>
#define N 220

using namespace std;

int CityNum, RoadNum;
int map[N][N], dis[N];
bool vis[N];

void Init(){
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < CityNum; i ++){
		dis[i] = 0xfffffff;
		for(int j = 0; j < CityNum; j ++){
			map[i][j] = 0xfffffff;
		}
	}
}

void SPFA(int start){
	queue<int>q;
	q.push(start);
	dis[start] = 0;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		vis[cur] = 0;
		
		for(int i = 0; i < CityNum; i ++){
			if(dis[i] > map[cur][i] + dis[cur]){
				dis[i] = map[cur][i] + dis[cur];
				if(!vis[i]){
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}	
}

int main()
{
	int start, end, len;
	while(scanf("%d%d", &CityNum, & RoadNum) != EOF){
		Init();
		for(int i = 0; i < RoadNum; i ++){
			scanf("%d%d%d", &start, &end, &len);
			if(map[start][end] > len){
				map[start][end] = map[end][start] = len;
			}
		}
		scanf("%d%d", &start, &end);
		
		SPFA(start);
		
		if(dis[end] == 0xfffffff){
			printf("-1
");
		}
		else{
			printf("%d
", dis[end]);
		}
	}
	
	return 0;
}