51nod 1459 迷宫游戏(dij)

题目链接：51nod 1459 迷宫游戏

dij裸题。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define CLR(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 const int inf = 0x3f3f3f3f;

 const int N = ;

 int d[N], vis[N];

 int a[N];//存每个房间的得分

 int ans[N]; //记录所经过的点的权值和

 int n, m, st, ed;

 struct qnode{

     int v, c;

     qnode(int _v = ,int _c = ):v(_v),c(_c) {}

     bool operator < (const qnode &r)const{

         return r.c < c;

     }

 };

 struct Edge{

     int v, w;

     Edge(int _v = , int _w = ):v(_v),w(_w) {}

 };

 vector<Edge>E[N];

 void addedge(int u, int v, int w){

     E[u].push_back(Edge(v, w));

 }

 void dij(){

     priority_queue<qnode>q;

     for(int i = ; i < n; ++i){

         d[i] = inf;

         vis[i] = ;

         ans[i] = ;

     }

     d[st] = ;

     ans[st] = a[st];

     q.push(qnode(st, ));

     while(!q.empty()){

         qnode t = q.top(); q.pop();

         int u = t.v;

         if(vis[u])

             continue;

         vis[u] = ;

         for(int i = ; i < E[u].size(); ++i){

             int v = E[u][i].v;

             int w = E[u][i].w;

             if(!vis[v] && d[u] + w < d[v]){

                 d[v] = d[u] + w;

                 ans[v] = ans[u] + a[v];

                 q.push(qnode(v, d[v]));

             }

             else if(!vis[v] && d[u] + w == d[v]){

                 ans[v] = max(ans[v], ans[u] + a[v]);

             }

         }

     }

 }

 int main(){

     int x, y, z;

     scanf("%d%d%d%d", &n, &m, &st, &ed);

     for(int i = ; i < n; ++i)

         scanf("%d", &a[i]);

     while(m--){

         scanf("%d%d%d", &x, &y, &z);

         addedge(x, y, z);

         addedge(y, x, z);

     }

     dij();

     printf("%d %d\n", d[ed], ans[ed]);

     return ;

 }