dijkstra.cpp

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct Edge {
    int value;
    int begin;
    int dest;
};
struct Node {
    int id;
    int shortest_length;
};

vector<Edge> list[1000];
int dis[1000];
bool visited[1000];

int main(){
    int n; //Edges
    int m; //Nodes
    while(cin>>n>>m){
        for(int i=0; i<m; ++i){
            list[i].clear();
            dis[i] = 1e9;
            visited[i] = false;
        }
        
        for(int i=0; i<n; i++){
            int beg, dest, value;
            Edge a, b;
            cin>>beg>>dest>>value;
            
            a.dest = dest;
            a.value = value;
            list[beg].push_back(a);
            
            b.dest = beg;
            b.value = value;
            list[dest].push_back(b);
        }
        /*
        // Print edges
        for(int i=0; i < n+1; i++){
            for(int j=0; j < list[i].size(); j++){
                cout<<i<<list[i][j].dest<<list[i][j].value<<endl;
            }
        }*/
        
        //Dijkstra
        
        //start from 0
        int source = 0;
        dis[source] = 0;
        
        for(int i=0; i<m; i++){
            int a = -1, min = 1e9;
            
            for(int j=0; j<m;j++){
                if(!visited[j] && dis[j] < min){
                    a = j;
                    min = dis[i];
                }
            }
            if(a == -1)
                break;
            
            visited[a] = true;

            for(int g=0; g < list[a].size(); g++){
                if(!visited[list[a][g].dest] && dis[list[a][g].dest] > dis[a] + list[a][g].value){
                    dis[list[a][g].dest] = dis[a] + list[a][g].value;
                }
            }
            
        }
        for(int i=0; i<m; i++){
            cout<<i<<' '<<dis[i]<<endl;
        }
        
    }
    
}