51nod 1649 齐头并进 (djikstra求最短路径，只用跑一次)

题目：

这道题有一个坑点：两种交通工具同时出发，中途不能停留在同一个小镇。

其实想通了就很简单，因为要么火车一步到达，要么汽车一步到达。不可能停留在同一个地方。

可是我还WA了好几次，蠢哭。想用BFS写，一直TLE，后来想到这点之后，用djikstra求单源最短路径就出来了。

如果火车一步到，就求汽车的单源最短路径；如果汽车一步到，就求火车的单源最短路径。

代码：

#include <iostream>

#include <algorithm>

#include <map>

#include <vector>

#include <set>

#include <math.h>

#include <queue>

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

typedef long long ll;

//#define INF 2147483647

#define INF 2000000000

int n,m;

#define MAX_V 410

int cost[MAX_V][MAX_V];  //cost[u][v]表示e = (u,v)的权值

int d[MAX_V];        //源点s出发的最短距离

bool used[MAX_V];    //标记使用过的点 

int djikstra(){

    fill(d,d+n+,INF);

    fill(used,used+n,false);

    d[] = ;

    while(true){

        int v = -;

        for(int i = ;i <= n; i++){

            if(!used[i]&&(v == - || d[i] < d[v])) v = i;

        }

        if(v == -) break;

        used[v] = true;

        for(int i = ;i <= n; i++){

            if(cost[v][i] == ){

                d[i] = min(d[i],d[v]+cost[v][i]);

            }

        }

    }

    if(d[n] == INF) return -;

    else return d[n];

}

int main() {

    cin >> n >> m;

    for(int i = ;i <= n; i++){

        for(int j = ;j <= n; j++){

            cost[i][j] = -;

            if(i == j) cost[i][j] = ;

        }

    }

    for(int i = ;i <= m; i++){

        int u,v;

        cin >> u >> v;

        cost[u][v] = ;

        cost[v][u] = ;

    }

    if(cost[][n] == ){

        for(int i = ;i <= n; i++){

            for(int j = ;j <= n; j++){

                cost[i][j] = -cost[i][j];

            }

        }

    }

    cout << djikstra() << endl;

    return ;

}

巴特西

51nod 1649 齐头并进 (djikstra求最短路径，只用跑一次)

最新文章

热门文章