PAT_甲级_1111 Online Map (30point(s)) (C++)【Dijkatra+DFS】

目录

1，题目描述

 题目大意

说明

2，思路

算法

3，AC代码

4，解题过程

---

1，题目描述

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

 题目大意

 

说明

• one-way is 1 if the street is one-way from V1 to V2：当one-way是1时，V1到V2是单行道；
• one-way说明为有向图；
• 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：当最短的路和最快的路重合时，合并输出；

 

2，思路

emmm没有对相同的部分进行合并（虽然Dijkstra和DFS原理相同，但是还是有细节的区别），还是直接copy一遍，改点变量简单点，不足就是代码长了一点，哈哈哈。

算法

1. Dijkstra求出所有最短路径：                                   
2. DFS遍历所有最短路径，并找出耗时最短的一条：             
3. Dijkstra求出所有最快路径：                                                 
4. DFS遍历所有最短路径，并找出经过节点最少的一条：                                 
5. 自定义比较函数cmp1比较两个vector是否相同：
6. 设计输出函数（用于简化输出）：

 

3，AC代码

最长的一次代码了。。。（第一次超过100行）

#include<bits/stdc++.h>
using namespace std;
int N, M;
bool visited[510];
int disGraph[510][510], timeGraph[510][510];
int d1, d2, dis[510];//d1起点 d2终点
vector<int> disPath, timePath, tem;
vector<int> pre[510];

int minTime = INT_MAX, minNum = INT_MAX;
void dfsDis(int start, int time){       //对若干条最 短 路径DFS
    tem.push_back(start);
    if(start == d1){
        if(time < minTime){
            disPath = tem;
            minTime = time;
        }
    }
    for(int i = 0; i < pre[start].size(); i++)
        dfsDis(pre[start][i], time + timeGraph[pre[start][i]][start]);// !!!timeGraph[pre[start][i]][start]顺序:先pre[start][i] 后start
    tem.pop_back();
}
void dfsTime(int start, int num){       //对若干条最 快 路径DFS
    tem.push_back(start);
    if(start == d1){
        if(num < minNum){
            timePath = tem;
            minNum = num;
        }
    }
    for(int i = 0; i < pre[start].size(); i++)
        dfsTime(pre[start][i], num + 1);
    tem.pop_back();
}
void display(vector<int> v){
    printf("%d", v[v.size()-1]);
    for(int i = v.size() - 2; i >= 0; i--)
        printf(" -> %d", v[i]);
}
bool cmp1(vector<int> a, vector<int> b){
    for(int i = 0; i < a.size() && i < b.size(); i++){
        if(a[i] != b[i])
            return false;
    }
    return true;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    cin>>N>>M;
    int one_way, len, time;
    fill(disGraph[0], disGraph[0] + 510 * 510, INT_MAX);// !!!写成disGraph[0] + N * N时会出错(无法赋值)
    fill(timeGraph[0], timeGraph[0] + 510 * 510, INT_MAX);
    for(int i = 0; i < M; i++){
        scanf("%d %d %d %d %d", &d1, &d2, &one_way, &len, &time);
        disGraph[d1][d2] = len;
        timeGraph[d1][d2] = time;
        if(one_way == 0){
            disGraph[d2][d1] = len;
            timeGraph[d2][d1] = time;
        }
    }
    scanf("%d %d", &d1, &d2);

    //Dijkstra最短路
    fill(visited, visited + N, false);
    fill(dis, dis + N, INT_MAX);
    dis[d1] = 0;
    for(int i = 0; i < N; i++){
        int minDis = INT_MAX, u = -1;
        for(int j = 0; j < N; j++){
            if(!visited[j] && minDis > dis[j]){
                u = j;
                minDis = dis[j];
            }
        }
        if(u == -1) break;
        visited[u] = true;
        for(int v = 0; v < N; v++){
            if(!visited[v] && disGraph[u][v] < INT_MAX){
                if(dis[v] > dis[u] + disGraph[u][v]){
                    dis[v] = dis[u] + disGraph[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + disGraph[u][v])
                    pre[v].push_back(u);
            }
        }
    }
    int D = dis[d2];
    tem.clear();
    dfsDis(d2, 0);

    //Dijkstra最快路
    for(int i = 0; i < 510; i++)
        pre[i].clear();             // !!!
    fill(visited, visited + N, false);
    fill(dis, dis + N, INT_MAX);
    dis[d1] = 0;
    for(int i = 0; i < N; i++){
        int minDis = INT_MAX, u = -1;
        for(int j = 0; j < N; j++){
            if(!visited[j] && minDis > dis[j]){
                u = j;
                minDis = dis[j];
            }
        }
        if(u == -1) break;
        visited[u] = true;
        for(int v = 0; v < N; v++){
            if(!visited[v] && timeGraph[u][v] < INT_MAX){
                if(dis[v] > dis[u] + timeGraph[u][v]){
                    dis[v] = dis[u] + timeGraph[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + timeGraph[u][v])
                    pre[v].push_back(u);
            }
        }
    }
    tem.clear();            // !!!
    int T = dis[d2];
    dfsTime(d2, 1);
    if(cmp1(disPath, timePath)){
        printf("Distance = %d; Time = %d: ", D, T);
        display(disPath);
    }else{
        printf("Distance = %d: ", D);
        display(disPath);
        printf("\nTime = %d: ", T);
        display(timePath);
    }
    return 0;
}

4，解题过程

虽然编写过程挺秃然的，但好歹没有很坑的数据：

一发入魂o(*￣▽￣*)ブ