HDU 2680 Choose the best route 最短路、Dijkstra、多源化单源最短路

Source

UESTC 2016 Summer Training #13 Div.2

HDU 2680

My Solution

最短路

有多个起点， 设为 g[0][i] = 0, 这样Dijkstra的 dist[i] 表示的是0 到 i的最短路径，

并且这样一设置 0 - 那些起点的路径长度就是0了，所以就当作起点是0，

化为了单源最短路

所以跑一遍Dijkstra就好了

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 8;
const int INF = 1e9 + 7;


//!dijkstra的版来自红书
int n, g[maxn][maxn], v[maxn],dist[maxn];
int dijkstra()
{

    for(int i = 1; i <= n; i++) dist[i]=INF;
    //dist[1] = 0;
    memset(v, 0, sizeof v);
    //!
    for(int i = 1; i <= n; i++){
        dist[i] = g[0][i];
    }
    for(int i = 1; i <= n; i++){
        int mark = 0, mindis=INF;
        for(int j = 1; j <= n; j++){
            if(!v[j] && dist[j] < mindis){
                mindis = dist[j];
                mark = j;
            }
        }
        v = 1;
        if(mindis == INF) return INF;
        for(int j = 1; j <= n; j++){
            if(!v[j]){
                dist[j] = min(dist[j], dist + g[j]);
            }
        }
    }
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freoven("b.txt", "w", stdout);
    #endif // LOCAL
    int m, d, w, start;
    int p, q, t;
    while(scanf("%d%d%d", &n, &m, &d) != EOF){
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                g[i][j] = INF;
            }
        }
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d", &p, &q, &t);
            if(t < g[p][q])
                g[p][q] = t;
        }
        scanf("%d", &w);
        for(int i = 0; i < w; i++){
            scanf("%d", &start);
            g[0][start] = 0;
        }

        dijkstra();
        if(dist[d] == INF)
           printf("-1n");
        else
           printf("%dn", dist[d]);

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx