图论_最短路_dij_heap.cpp

一些ACM基本算法的测试源码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int SIZE = 1001;
const int INF = 1000000000;

int n; //n个顶点
bool visit[SIZE];
int dist[SIZE];

struct Node{
    int to, w;  
    Node(int tto, int tw) : to(tto),  w(tw) {}     
};

vector<Node>edge[SIZE];

struct cmp{
    bool operator () (const Node &a, const Node &b)
    {
        return a.w > b.w;     
    }       
};
//顶点坐标从0开始
void Dijkstra(int s) //从点s到其它各点的最短距离，保存在数组dist中
{
    int i, j, curs, v, w;
    priority_queue <Node, vector<Node>, cmp> q;
    Node tmp(s, 0);
    for(i = 0; i < n; i ++)
    {
        dist[i] = INF;
        visit[i] = false;      
    }         
    dist[s] = 0;
    q.push(tmp);
    for(i = 0; i < n; i ++)
    {
        while(1)
        {
            tmp = q.top();
            q.pop();
            if(!visit[tmp.to])
            {
                visit[tmp.to] = true;
                break;                  
            }
        }
        curs = edge[tmp.to].size();
        for(j = 0; j < curs; j ++)
        {
            v = edge[tmp.to][j].to;
            w = edge[tmp.to][j].w;
            if(!visit[v] && dist[v] > dist[tmp.to] + w)
            {
                dist[v] = dist[tmp.to] + w;
                q.push(Node(v, dist[v]));             
            }      
        }
    }
}

int main()
{
    int m;//m条边 
    int u, v, w;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++)
    {
        scanf("%d%d%d", &u, &v, &w);
        edge[u].push_back(Node(v, w));  
        /*无向图 
        edge[v].push_back(Node(u, w));
        */ 
    }        
    Dijkstra(0);
    for(int i = 0; i < n; i ++)
        printf("%d\n", dist[i]);
    system("pause");
    return 0;
}