Heavy Transportation POJ - 1797

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>

using namespace std;
/*迪杰斯特拉算法为啥不能有负边
   因为你要保证从队列中取出来的最小的点x一定是该节点到原点的最短距离
   如果有负边，那么可能比他大的y点再加上负边导致x结点距离变得更小
   这道题利用了迪杰斯特拉的思想
*/
const int  INF=0x3f3f3f3f;
const int maxn=1000+10;
int dis[maxn],vis[maxn];
struct Node
{
    int v,value;
    Node()
    {

    }
    Node(int a,int b)
    {
        v=a;
        value=b;
    }
    bool operator<(const Node &d)const
    {
        return value<d.value;
    }
};
vector<Node>G[maxn];
void dji()
{
    priority_queue<Node> que;
    que.push(Node(1,INF));
    while(!que.empty())
    {
        Node node=que.top();
        que.pop();
        if(vis[node.v])
            continue;
        vis[node.v]=1;
        int v=node.v;
        dis[v]=node.value;
        for(int i=0; i<G[v].size(); i++)
        {
            Node node1=G[v][i];
            int v1=node1.v;
            dis[v1]=max(dis[v1],min(dis[v],G[v][i].value));

            que.push(Node(v1,dis[v1]));
        }
    }

}
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    int kase=0;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int a,b,c;
        memset(dis,0,sizeof dis);
        memset(vis,0,sizeof vis);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            G[a].push_back(Node(b,c));
            G[b].push_back(Node(a,c));
        }
        dji();
        printf("Scenario #%d:\n%d\n",++kase,dis[n]);

    }
    return 0;
}