kuangbin_ShortPath K (POJ 3159)

很简单的模板题 放在K那么后的位置的原因大概是 光看题意并不是很容易想到是用最短路解吧

奈何kuangbin分在了最短路专题 一发水过

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std;

const int MAXN = 3e4 + 10;
const int MAXM = 15e4 + 10;

typedef pair<int, int> pii;
struct cmp{
    bool operator () (const pii a, const pii b){
        return a.first > b.first;
    }
};

int size, head[MAXN], val[MAXM], point[MAXM], nxt[MAXM];
int n, m, dis[MAXN];

inline void add(int from, int to, int value)
{
    val[size] = value;
    point[size] = to;
    nxt[size] = head[from];
    head[from] = size++;
}

void dij(int s, int t)
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(0, s));
    dis[s] = 0;
    while(!q.empty()){
        pii u = q.top();
        q.pop();
        if(u.first > dis[u.second]) continue;
        for(int i = head[u.second]; ~i; i = nxt[i]){
            int j = point[i];
            if(dis[j] > dis[u.second] + val[i]){
                dis[j] = dis[u.second] + val[i];
                q.push(make_pair(dis[j], j));
            }
        }
    }
    printf("%d
", dis[t]);
}
int main()
{
    memset(head, -1, sizeof head);
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, value;
        scanf("%d%d%d", &a, &b, &value);
        add(a, b, value);
    }
    dij(1, n);
    return 0;
}