데이터 구조 (23)

07 - 그림 6 관광 계획 (25 분 하 다
자가 운전 여행 노선 도 를 보면 도시 간 고속도로 길이 와 이 도로 에서 받 아야 할 통행 료 를 알 수 있 을 것 이다.지금 은 상담 하 러 온 관광객 들 이 출발지 와 목적지 사이 의 가장 짧 은 경 로 를 찾 을 수 있 도록 프로그램 을 써 야 한다.만약 몇 개의 경로 가 모두 가장 짧다 면, 가장 싼 경 로 를 출력 해 야 한다.
입력 형식:
입력 설명: 입력 데이터 의 첫 번 째 줄 은 4 개의 정수 N, M, S, D 를 제시 합 니 다. 그 중에서 N (2 ≤ N ≤ 500) 은 도시 의 개수 이 고 도시 의 번호 가 0 이 라 고 가정 합 니 다 ~ (N - 1).M 은 고속도로 의 개수 이다.S 는 출발지 의 도시 번호 이다.D 는 목적지 의 도시 번호 다.그 다음 에 M 줄 에서 각 줄 은 고속도로 정 보 를 주 었 는데 그것 이 바로 도시 1, 도시 2, 고속도로 길이, 요금 액 이다. 중간 에 빈 칸 으로 나 누 면 숫자 는 모두 정수 이 고 500 을 초과 하지 않 는 다.보증 해 의 존 재 를 입력 하 십시오.
출력 형식:
한 줄 에서 출력 경로 의 길이 와 비용 총액 은 숫자 간 에 빈 칸 으로 구분 되 며 출력 끝 에 빈 칸 이 있어 서 는 안 됩 니 다.
입력 예시:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

출력 예시:

3 40

#include   
#include   
#define N 500  
#define INF 501  
int g[N][N][2], dis[N + 1], known[N], pay[N];  
int main() {  
    int n, m, s, d, i, j, t1, t2, v;  
    scanf("%d%d%d%d", &n, &m, &s, &d);  
    for (i = 0;i < n;i++) {  
        for (j = 0;j < n;j++) {  
            g[i][j][0] = INF;  
            g[i][j][1] = INF;  
        }  
    }  
    while (m--) {  
        scanf("%d%d%d%d", &i, &j, &t1, &t2);  
        g[i][j][0] = g[j][i][0] = t1;  
        g[i][j][1] = g[j][i][1] = t2;  
    }  
      
    memset(known, 0, n*sizeof(int));  
    for (j = 0;j < n;j++) {  
        dis[j] = g[s][j][0];  
        pay[j] = g[s][j][1];  
    }  
    dis[s] = 0;  
    pay[s] = 0;  
    dis[n] = INF;  
      
    while (1) {  
        v = n;  
        for (i = 0;i < n;i++) {  
            if (!known[i] && dis[i] < dis[v])  
                v = i;  
        }  
        if (v == n) break;  
        known[v] = 1;  
        for (i = 0;i < n;i++) {  
            if (!known[i] && g[v][i][0] < INF) {  
                if (dis[v] + g[v][i][0] < dis[i]) {  
                    dis[i] = dis[v] + g[v][i][0];  
                    pay[i] = pay[v] + g[v][i][1];  
                }  
                else if (!known[i] && dis[v] + g[v][i][0] == dis[i] &&  
                    pay[v] + g[v][i][1] < pay[i]) {  
                    pay[i] = pay[v] + g[v][i][1];  
                }  
            }  
        }  
    }  
    if(dis[d] < INF)  
        printf("%d %d", dis[d], pay[d]);      
    return 0;  
}