這道題我讀題不仔細導(dǎo)致踩了個大坑，一個測試點過不了卡了好幾個小時：第二個dijkstra算法中，題目要求是“In case the fastest path is not unique, output the one that passes through the fewest intersections”，我卻想當然地認為在fastest path is not unique的時候，判斷標準是最短距離……

#include <cstdio>
#include <vector>
#include <algorithm>
const int MAXN = 501;
const int INF = 999999999;

int N, M, u, v, oneWay, a, b, src, dst, tmp;
int dist[MAXN][MAXN];
int time[MAXN][MAXN];
int path[MAXN];
std::vector<int> d1, t1, t2, path1, path2;

void dijkstra1(int k){
    int minDist, pivot;
    d1.resize(N, INF);
    t1.resize(N, INF);
    std::vector<bool> visited(N);
    std::fill(visited.begin(), visited.end(), false);
    std::fill(path, path + N, -1);
    d1[k] = 0;
    t1[k] = 0;
    for(int i = 0; i < N; ++i){
        pivot = -1;
        minDist = INF;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && d1[j] < minDist){
                pivot = j;
                minDist = d1[j];
            }
        }
        if(pivot == -1){
            return;
        }
        visited[pivot] = true;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && dist[pivot][j] < INF && d1[pivot] + dist[pivot][j] < d1[j]){
                d1[j] = d1[pivot] + dist[pivot][j];
                t1[j] = t1[pivot] + time[pivot][j];
                path[j] = pivot;
            } else if(!visited[j] && dist[pivot][j] < INF && time[pivot][j] < INF
                && d1[pivot] + dist[pivot][j] == d1[j] && t1[pivot] + time[pivot][j] < t1[j]){
                t1[j] = t1[pivot] + time[pivot][j];
                path[j] = pivot;
            }
        }
    }
}

void dijkstra2(int k){
    int minTime, pivot;
    t2.resize(N, INF);
    std::vector<int> intersection(N, INF);
    std::vector<bool> visited(N);
    std::fill(visited.begin(), visited.end(), false);
    std::fill(path, path + N, -1);
    intersection[k] = 0;
    t2[k] = 0;
    for(int i = 0; i < N; ++i){
        pivot = -1;
        minTime = INF;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && t2[j] < minTime){
                pivot = j;
                minTime = t2[j];
            }
        }
        if(pivot == -1){
            return;
        }
        visited[pivot] = true;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && time[pivot][j] < INF && t2[pivot] + time[pivot][j] < t2[j]){
                t2[j] = t2[pivot] + time[pivot][j];
                intersection[j] = intersection[pivot] + 1;
                path[j] = pivot;
            } else if(!visited[j] && time[pivot][j] < INF
                && t2[pivot] + time[pivot][j] == t2[j] && intersection[pivot] + 1 < intersection[j]){
                intersection[j] = intersection[pivot] + 1;
                path[j] = pivot;
            }
        }
    }
}

int main(){
    std::fill(dist[0], dist[0] + MAXN * MAXN, INF);
    std::fill(time[0], time[0] + MAXN * MAXN, INF);
    scanf("%d %d", &N, &M);
    for(int i = 0; i < M; ++i){
        scanf("%d %d %d %d %d", &u, &v, &oneWay, &a, &b);
        dist[u][v] = a;
        time[u][v] = b;
        if(!oneWay){
            dist[v][u] = a;
            time[v][u] = b;
        }
    }
    scanf("%d %d", &src, &dst);
    dijkstra1(src);
    tmp = dst;
    while(path[tmp] != -1){
        path1.push_back(tmp);
        tmp = path[tmp];
    }
    dijkstra2(src);
    tmp = dst;
    while(path[tmp] != -1){
        path2.push_back(tmp);
        tmp = path[tmp];
    }
    if(path1 == path2){
        printf("Distance = %d; Time = %d: %d", d1[dst], t1[dst], src);
        for(int i = path1.size() - 1; i >= 0; --i){
            printf(" -> %d", path1[i]);
        }
    } else{
        printf("Distance = %d: %d", d1[dst], src);
        for(int i = path1.size() - 1; i >= 0; --i){
            printf(" -> %d", path1[i]);
        }
        printf("\nTime = %d: %d", t2[dst], src);
        for(int i = path2.size() - 1; i >= 0; --i){
            printf(" -> %d", path2[i]);
        }
    }
    return 0;
}

題目如下：

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers?N?(2≤N≤500), and?M, being the total number of streets intersections on a map, and the number of streets, respectively. Then?M?lines follow, each describes a street in the format:

V1 V2 one-way length time

where?V1?and?V2?are the indices (from 0 to?N?1) of the two ends of the street;?one-way?is 1 if the street is one-way from?V1?to?V2, or 0 if not;?length?is the length of the street; and?time?is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance?D?in the format:

Distance = D: source -> v1 -> ... -> destination

Then in the next line print the fastest path with total time?T:

Time = T: source -> w1 -> ... -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:文章來源地址http://www.zghlxwxcb.cn/news/detail-468927.html

Distance = D; Time = T: source -> u1 -> ... -> destination

Sample Input 1:

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5

Sample Output 1:

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

Sample Input 2:

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5

Sample Output 2:

Distance = 3; Time = 4: 3 -> 2 -> 5

到了這里，關(guān)于1111 Online Map （PAT甲級）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！