//前向星

struct node {

    int nxt;

    int val;

    int lst;

    node () {}

    node (int next, int value) : nxt(next), val(value) {}

};

struct headnode {

    int u;

    int val;

    headnode () {}

    headnode (int uu, int value) : u(uu), val(value) {}

    bool operator < (const headnode &a) const {

        return val > a.val;

    }

};  // 用于优先队列而已。val是比较的值。dist[i]

int dist[maxn];

bool vis[maxn];

node edge[maxn];

int  last[maxn]

void Dij()

{

    memset(dist, 0x3f, sizeof(dist));

    memset(vis,  ,    sizeof(vis));

    priority_queue<headnode> pq;

    pq.push(headnode(, ));

    dist[] = ;

    headnode now;

    while (!pq.empty()) {

        now = pq.top(); pq.pop();

        if (vis[now.u]) continue;

        vis[now.u] = true;

        for (int i=last[now.u]; i!=-; i=edge[i].lst) {

            if (dist[edge[i].nxt] > edge[i].val + dist[now.u]) {

                dist[edge[i].nxt] = edge[i].val + dist[now.u];

                pq.push(headnode(edge[i].nxt, dist[edge[i].nxt]));

            }

        }

    }

}