link

Dijkstra无优化版本 (AC)

/**********************************************************
    > File Name : 2384.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 18 19:01:57
**********************************************************/
// 邻接矩阵表示 141ms
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#define INF 1<<28
using namespace std;
int map[1050][1050];
int t, n;
int d[1050];
bool used[1050];
void bell(int f){
    fill(d, d + n + 1, INF);
    memset(used, 0, sizeof(used));
    d[f] = 0;

    while(true){
        int v = -1;
        for(int u = 1;  u < n + 1; u++){
            if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
        }
        if(v == -1) break;
        used[v] = true;
        for(int u = 1; u < n + 1; u++){
            d[u] = min(d[u], d[v] + map[v][u]);
        }
    }
}
int main(){
    while(cin >> t >> n){
        int a, b, c;
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                map[i][j] = INF;
            }
        }
        for(int i = 0; i < t; i++){
            cin >> a >> b >> c;
            if(c < map[a][b]){
                map[a][b] = c;
                map[b][a] = c;
            }
        }
        for(int i = 0; i < n + 1; i++){
            map[i][i] = 0;
        }
        bell(1);
        cout << d[n] << endl;
    }
    return 0;
}

Dijkstra 邻接表 + 堆优化 (AC)

/**********************************************************
    > File Name : 2384.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 18 19:01:57
**********************************************************/
// 邻接表表示+堆优化 141ms
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#define INF 1<<28
using namespace std;
struct road{int to, cost; };
// first为最短距离, second为编号
typedef pair<int, int> P;
int n, t;
vector<road> G[1010];
int d[1010];

void dij(int f){
    //优先队列 首先按照pair.first进行排序, first相同时按照second进行排序
    priority_queue<P, vector<P>, greater<P> > q;
    fill(d, d + n + 1, INF);
    d[f] = 0;
    q.push(P(0, f));

    while (!q.empty()) {
        //每次选择出距离f最近的点为v
        P p = q.top();
        q.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        // 以v为跳板更新其他边的最小距离
        for(int i = 0; i < G[v].size(); i++){
            road e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                q.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    while (cin >> t >> n) {
        int a, b, c;
        // 邻接表的输入
        for (int i = 0; i < t; i++) {
            cin >> a >> b >> c;
            road tmp;
            tmp.to = b;
            tmp.cost = c;
            //将各个边push进G[a]
            G[a].push_back(tmp);
            tmp.to = a;
            tmp.cost = c;
            //将各个边push进G[b]
            G[b].push_back(tmp);
        }
        dij(1);
        cout << d[n] << endl;
    }
    return 0;
}