Dijkstra算法堆优化(vector建图)

佚名 6年前 (2018-10-08) 算法 1486人围观抢沙发百度已收录

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<queue>
#include <vector>
#include <map>
int s,t;
int n,m;
using namespace std;
const int INF=99999999;
struct Node{
    int to;
    int w;
};
struct Node temp;
vector<Node> v[1002];
typedef pair<int, int> P;
int dis[1002];
void Dijkstra(){
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    priority_queue<P,vector<P>,greater<P> >que;
    que.push(P(0,1));
    dis[1]=0;
    while(!que.empty()){
        P p=que.top();que.pop();
        if(dis[p.second]<p.first)
            continue;
        for(int i=0;i<v[p.second].size();i++){
            if(dis[v[p.second][i].to]>dis[p.second]+v[p.second][i].w){
                dis[v[p.second][i].to]=dis[p.second]+v[p.second][i].w;
                que.push(P(dis[v[p.second][i].to],v[p.second][i].to));
            }
        }
    }
}
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        v[i].clear();
    for(int i=1;i<=m;i++){
            cin>>s>>temp.to>>temp.w;
            v[s].push_back(temp);
    }
    Dijkstra();
    cout<<dis[6];
    return 0;
}