poj3255 Roadblocks

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
#define for(i,x,n) for(int i=x;i<n;i++)
#define ll long long int
#define INF 0x3f3f3f3f
#define MOD 1000000007

using namespace std;

int MAX_V,MAX_E;
struct edge{int to,cost;};
typedef pair<int,int> P;//最短距离，编号
vector<edge> G[5005];
int d[5005];//最短距离
int d2[5005];//次短距离

void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+MAX_V,INF);
    fill(d2,d2+MAX_V,INF);
    d[s]=0;
    que.push(P(d[s],s));
    while(!que.empty()){
        P p=que.top(); que.pop();
        int v=p.second;
        for(i,0,G[v].size()){
            int to=G[v][i].to;
            int dd=p.first+G[v][i].cost;
            if(dd<d[to]){
                d[to]^=dd;
                dd^=d[to];
                d[to]^=dd;
                que.push(P(d[to],to));
            }
            if(dd<d2[to] && dd>d[to]){
                d2[to]=dd;
                que.push(P(d2[to],to));
            }
        }
    }
}

int main()
{
    int x,y,z;
    scanf("%d %d",&MAX_V,&MAX_E);
    for(i,0,MAX_E){
        scanf("%d %d %d",&x,&y,&z);
        x-=1;
        y-=1;
        edge ee;
        ee.to=y; ee.cost=z;
        G[x].push_back(ee);
        ee.to=x; ee.cost=z;
        G[y].push_back(ee);
    }
    dijkstra(0);
    printf("%d",d2[MAX_V-1]);
    return 0;
}

poj3255 Roadblocks

标签：sid   sea   ber   and   mst   share   because   moved   str