dijkstra.cpp

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int oo = 1000111000;

vector< pair <int, int> > a[2309];
int n, m;

int d[2309];

void dijkstra()
{
    priority_queue< pair <int, int> , vector< pair <int, int> >, greater< pair <int, int> > > pq;
    int i, u, v, du, uv;

    for (i = 1; i <= n; i++)
        d[i] = oo;
    d[1] = 0;
    pq.push( pair <int, int> (0, 1));

    while (pq.size())
    {
        u = pq.top().second;
        du = pq.top().first;
        pq.pop();
        if (du != d[u])
            continue;

        for (i = 0; v = a[u][i].second; i++)
        {
            uv = a[u][i].first;
            if (d[v] > du + uv)
            {
                d[v] = du + uv;
                pq.push( pair <int, int> (d[v], v));
            }
        }
    }
}

main()
{
    int p, q, i, m, w;
    scanf("%d%d", &n, &m);
    while (m--)
    {
        scanf("%d%d%d", &p, &q, &w);
        a[p].push_back( pair <int, int> (w, q));
        a[q].push_back( pair <int, int> (w, p));
    }
    for (i = 1; i <= n; i++)
        a[i].push_back( pair <int, int> (0, 0));
    dijkstra();
    for (i = 1; i <= n; i++)
        printf("d( 1 -> %d ) = %d\n", i, d[i]);
}

mirror.cpp

#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <climits>
#include <set>
#include <utility>

typedef ssize_t llint;
typedef size_t ullint;

// Dijkstra's algorithm to find shortest path between two vertices in a graph,
// using adjacency list representation

const long long int MAX = INT64_MAX;

// Note that the index of each vertex counts from 0.

std::vector<bool> traversed;
// log if a specific vertex has been checked
// preventing infinite loop

struct edge
{
    llint weight, targetVertex;
    // for each vertex
    // its adjacency list entry will contain informations about its neighbour(s)
    // including the weight of the edge connecting them
};

std::vector<llint> dijkstra(llint source, llint target, std::vector<std::vector<edge>> adjacencyList)
{
    
}

std::vector<std::vector<edge>> adjacencyList;

int main()
{
	llint verticesCount;
	std::cin >> verticesCount;
	// prepare traversal logging and adjacency list
	traversed.resize(verticesCount);
	adjacencyList.resize(verticesCount);

	for (llint i = 0; i < verticesCount; i++)
	{
		llint neighbour_count;
		std::cin >> neighbour_count;
		while (neighbour_count-- > 0)
		{
			// edge between vertex[i] and vertex[push.targetVertex] with weight = push.weight
			edge push;
			std::cin >> push.targetVertex >> push.weight;
			adjacencyList[i].push_back(push);
		}
	}
	std::vector<llint> out = dijkstra(0, 4, adjacencyList);
	for (const llint &i : out)
		std::cout << (i != MAX ? std::to_string(i) : std::string("MAX")) << " ";
}

/*
Input specification:
number_of_vertex
number_of_edges edge1_other_vertex edge1_weight edge2_other_vertex edge2_weight ...
...
Output specification:
distance from source (here I use 0) to each other vertex starting from vertex 0.
an output of MAX indicates that it is impossible to reach the corresponding vertex.
Test:
{input}
6
2 1 1 2 1
2 3 1 2 1
2 3 1 5 1
1 4 1
0
0
{output}
4 3 1
*/