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;
}