图论_最短路_dij_邻接表.cpp

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

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

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

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

struct Node
{
    int to, w;       
};

vector<Node>graph[SIZE];
//顶点坐标从0开始 
void Dijkstra(int s)//从点s到其它各点的最短距离，保存在数组dist中 
{
    int i, j, minvalue, tmp, curs, v, w;
    for(i = 0; i < n; i ++)
    {
        dist[i] = INF;
        visit[i] = false;      
    }         
    dist[s] = 0;
    for(i = 0; i < n; i ++)
    {
        minvalue = INF;
        for(j = 0; j < n; j ++)
            if(!visit[j] && minvalue > dist[j])
            {
                minvalue = dist[j];
                tmp = j;
            } 
        visit[tmp] = true;
        curs = graph[tmp].size();
        for(j = 0; j < curs; j ++)
        {
            v = graph[tmp][j].to;
            w = graph[tmp][j].w;
            if(!visit[v] && dist[v] > w + dist[tmp])
                dist[v] = w + dist[tmp];
        }
    }
}

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

/*
3 3
0 1 2
1 2 1
0 2 4
*/