POJ(1797)(Silver Cow Party)

链接：https://vjudge.net/problem/POJ-3268
思路：求1-n路径上最小边权值的最大值，用最短路模拟即可，只是d改为从根节点到当前节点边上边权值的最小值，注意此时要求最大值所以队列要出优先最大值，如果是求最大权值边的最小值则队列优先出最小值。
代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;

const int maxn = 1010;
int n,m;
int dp[maxn];

typedef pair<int,int> P;

struct edge{
    int from,to,dist;
    edge(){}
    edge(int f,int t,int d):from(f),to(t),dist(d){}
};

struct Dijkstra{
    int n,m;
    vector<edge> edges;
    vector<int> G[maxn];
    int d[maxn];
    int p[maxn];
    int vis[maxn];

    void init(int n){
     this->n = n;
     for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int dist){
        edges.push_back(edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);//放入的是edges中的编号
    }

    void dijkstra(){
        memset(vis,0,sizeof(vis));
    priority_queue<P,vector<P>,less<P> > Q;//优先队列最大值优先出队
    memset(d,0,sizeof(d));
    for(int i=0;i<=n;i++)d[i] = -1e9;
    d[0] = 1e9;
    Q.push(P(d[0],0));
    while(!Q.empty()){
        P p1 = Q.top();
        Q.pop();
        int v = p1.second;
        if(vis[v])continue;
        vis[v] = 1;
        for(int i=0;i<G[v].size();i++){
            edge& e = edges[G[v][i]];
            if(!vis[e.to]&&d[e.to]<min(d[v],e.dist)){
                d[e.to] = min(d[v],e.dist);
                Q.push(P(d[e.to],e.to));
            }
        }
    }
    }

    void output(int s,int e,vector<int>& path){
        int pos=e;
        while(1){
            path.push_back(pos);
            if(pos==s) break;
            pos=p[pos];
        }
    }
}solver;

int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d%d",&n,&m);
        solver.init(n);
        for(int j=0;j<m;j++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--;
            b--;
            solver.addedge(a,b,c);
            solver.addedge(b,a,c);
        }
        solver.dijkstra();
        printf("Scenario #%d:\n%d\n\n",i,solver.d[n-1]);
    }
    return 0;
}