A1111 Online Map (30分)(最短路径、Dijkstra+DFS)

一、技术总结

• 关于最短路径的问题，可以将问题化简，为两个部分，一个是单独使用Dijkstra求最短路径，然后再使用DFS进行第二判定条件再选出合适的路径；
• 其中推荐使用邻接表来存储图的信息，至于其他边权可以使用二维数组进行存储，如果点权直接使用结构体进行存储信息；
• 如果有多个判定条件，应该分别使用Dijkstra遍历图，被放在一个里面进行遍历；

二、参考代码

#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
const int INF = 10000000;
vector<int> G[maxn];
vector<int> preW[maxn], preT[maxn];
vector<int> tempPathW, tempPathT, pathW, pathT;
int w[maxn][maxn], t[maxn][maxn];
int d[maxn], c[maxn];
bool visW[maxn] = {false}, visT[maxn] = {false};
int optValueT = INF, optValueW = INF;
int n, m, st, ed;
void DijkstraW(int s){
    fill(d, d+maxn, INF);
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j < n; j++){
            if(visW[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;
        visW[u] = true;
        for(int j = 0; j < G[u].size(); j++){
            int v = G[u][j], l = w[u][v];
            if(visW[v] == false){
                if(d[u] + l < d[v]){
                    d[v] = d[u] + l;
                    preW[v].clear();
                    preW[v].push_back(u);
                }else if(d[u] + l == d[v]){
                    preW[v].push_back(u);
                }
            }
        }
    }
}
void DijkstraT(int s){
    fill(c, c+maxn, INF);
    c[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j < n; j++){
            if(visT[j] == false && c[j] < MIN){
                u = j;
                MIN= d[j];
            }
        }
        if(u == -1) return;
        visT[u] = true;
        for(int j = 0; j < G[u].size(); j++){
            int v = G[u][j], ti = t[u][v];
            if(visT[v] == false){
                if(c[u] + ti < c[v]){
                    c[v] = c[u] + ti;
                    preT[v].clear();
                    preT[v].push_back(u); 
                }else if(c[u] + ti == c[v]){
                    preT[v].push_back(u); 
                }
            }
        }
    }
}
void DFSW(int d){
    if(d == st){
        tempPathW.push_back(d);
        int value = 0;
        for(int i = tempPathW.size() - 1; i > 0; i--){
            int id = tempPathW[i], next = tempPathW[i-1];
            value += t[id][next];
        }
        if(value < optValueW){
            optValueW = value;
            pathW = tempPathW;
        }
        tempPathW.pop_back();
        return;
    }
    tempPathW.push_back(d);
    for(int i = 0; i < preW[d].size(); i++){
        DFSW(preW[d][i]);
    }
    tempPathW.pop_back();
}
void DFST(int d){
    if(d == st){
        tempPathT.push_back(d);
        if(tempPathT.size() < optValueT){
            optValueT = tempPathT.size();
            pathT = tempPathT;
        }
        tempPathT.pop_back();
        return;
    }
    tempPathT.push_back(d);
    for(int i = 0; i < preT[d].size(); i++){
        DFST(preT[d][i]);
    }
    tempPathT.pop_back();
}
int main(){
    cin >> n >> m;
    int v1, v2, flag, length, time;
    for(int i = 0; i < m; i++){
        scanf("%d%d%d%d%d", &v1, &v2, &flag, &length, &time);
        if(flag == 1){
            G[v1].push_back(v2);
            w[v1][v2] = length, t[v1][v2] = time;
        }else{
            G[v1].push_back(v2);
            G[v2].push_back(v1);
            w[v1][v2] = length, t[v1][v2] = time;
            w[v2][v1] = length, t[v2][v1] = time;
        }
    }
    cin >> st >> ed;
    DijkstraW(st);
    DijkstraT(st);
    DFSW(ed);
    DFST(ed);
    if(pathT == pathW){
        printf("Distance = %d; Time = %d: ", d[ed], c[ed]);
        for(int i = pathW.size() - 1; i >= 0; i--){
            printf("%d", pathW[i]);
            if(i != 0) printf(" -> ");
        }       
    }else{
        printf("Distance = %d: ", d[ed]);
        for(int i = pathW.size() - 1; i >= 0; i--){
            printf("%d", pathW[i]);
            if(i != 0) printf(" -> ");
            if(i == 0) printf("\n");
        }
        printf("Time = %d: ", c[ed]);
        for(int i = pathT.size() - 1; i >= 0; i--){
            printf("%d", pathT[i]);
            if(i != 0) printf(" -> ");
        }   
    }
    return 0;
}