ACM:HDU1874畅通工程续

#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"string"
#include"cstdio"
#include"vector"
#include"cmath"
#include"queue"
using namespace std;
typedef long long LL;
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define MX 401

/*/************************************************************* /*/
//     typedef pair PII;   //  pair
/*/*************************************************************
pair 默认对first升序，当first相同时对second升序；

类模板：template  struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

功能：pair将一对值组合成一个值，这一对值可以具有不同的数据类型（T1和T2）
两个值可以分别用pair的两个公有函数first和second访问。

************************************************************* /*/


const int dij_v=1e3;
const int dij_edge=1e4;

template //模版类。
struct Dijkstra {

typedef pair PII;   //  pair
struct Edge {
int v,nxt;
T w;
} E[dij_edge<<1];
int Head[dij_v],erear;
T dis[dij_v],INF;

void edge_init() {
memset(Head,-1);
erear=0;
}

void edge_add(int u,int v,T w) {
E[erear].v=v;
E[erear].w=w;
E[erear].nxt=Head[u];
Head[u]=erear++;
}

void run(int u) {
memset(dis,0x3f);
INF=dis[0];
priority_queue, greater >Q;  //优先队列
while(!Q.empty())Q.pop();
Q.push(PII(0,u));
dis[u]=0;
while(!Q.empty()) {
PII A=Q.top();
Q.pop();
int a=A.second;
if(A.first!=dis[a])continue;  //如果不在一棵最小生成树上，跳过。
for(int i=Head[a]; ~i; i=E[i].nxt) {
int v=E[i].v;
T w=E[i].w;

/*/********************Dijkstra算法核心************************* /*/
if(w+dis[a]dis[v]=dis[a]+w; // 如果不是就覆盖掉改点
Q.push(PII(dis[v],v)); // 记录进队列。
}
/*/************************************************************* /*/

}
}
}
};

Dijkstra dij;

int main() {
int n,m;
while(~scanf("%d%d",&n,&m)) {
dij.edge_init();
for(int i=1; i<=m; i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
dij.edge_add(u,v,w);
dij.edge_add(v,u,w);
}
int st,ed;
scanf("%d%d",&st,&ed);
dij.run(st);
if(dij.dis[ed]==dij.INF)puts("-1");
else printf("%d\n",dij.dis[ed]);
}
return 0;
}