Factory Pattern
Abstract Factory
Provide an interface for creating families of related or dependent objects without specifying their concrete classes.
Factory Method
Define an interface for creating an object, but let subclasses decide which class to instantiate.
Factory Pattern lets a class defer instantiation to the subclasses.

Singleton
Ensure a class only has one instance and provide a global point of access to it.

The Command Pattern
encapsulates a request as an object, thereby letting you parameterize other objects with different requests, queue or log requests, and support undoable operations.

The adapter pattern
Adapter Converts the interface of a class into aniother interface clients expect. Lets classes work together that couldnt otherwise because of incompatible interfaces.
Facade Provides a unified interface to a set of interfaces in a subsystem. Facade defines a higher-level interface that makes the subsystem easier to use.

 原来用stl的优先队列这么爽，比赛时候多用，heap太容易打错了，毕竟没ghost_wei那么bt(heap,就几行,都打烂了-_-)

pku3159:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1 << 28;
const int MAXN = 30010;

struct PQNode {
    int u, key;
    //pq默认用<判断优先级,key大优先,若要key小优先,则加上!或<改成>即可
    friend bool operator<(const PQNode &a, const PQNode &b) { return !(a.key < b.key); } 
    
};


int n, m;
vector<int> adjv[MAXN], adjw[MAXN];

int dijkstraPQ(int st, int en) {
    int i, v, w, dist[MAXN], chk[MAXN];
    priority_queue<PQNode> pq;
    PQNode tmp, cp;

    memset(chk, 0, sizeof(chk));
    for (i=0; i<n; i++) dist[i] = INF;

    dist[st] = 0; 
    tmp.u = st; tmp.key = 0;
    pq.push(tmp);
    while (!pq.empty()) {
        cp = pq.top();
        pq.pop();
        if (cp.u == en) return dist[en];
        if (chk[cp.u]) continue;
        chk[cp.u] = 1;
        for (i=0; i<adjv[cp.u].size(); i++) {
            v = adjv[cp.u][i]; w = adjw[cp.u][i];
            if (!chk[v] && (dist[v]==INF || dist[v]>cp.key+w)) {
                dist[v] = cp.key+w;
                tmp.u = v; tmp.key = dist[v];
                pq.push(tmp);
            }
        }
    }
    return -1;
}

int main() {
    int i, j, k, u, v, w;
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (i=0; i<m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        u--; v--;
        adjv[u].push_back(v);
        adjw[u].push_back(w);
    }
    printf("%d\n", dijkstraPQ(0, n-1));
    return 0;
}