dijstra_string

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 107;
const int INF = INT_MAX;


int N, E;
int adj[MAXN][MAXN];
bool vis[MAXN];
int parent[MAXN];
int dist[MAXN];

map<string, int> mark1;
map<int, string> mark2;

void init()
{
    for(int i=0; i<MAXN; i++)
    {
        dist[i] = INF;
        parent[i] = -1;
    }
}

struct Node
{
    int v, distance;
    Node(int v, int distance)
    {
        this->v = v;
        this->distance = distance;
    }
};

bool operator < (const Node &a, const Node &b)
{
    if(a.distance > b.distance) return true;
    else return false;
}


void dijstra(int src)
{
    dist[src] = 0;
    priority_queue<Node> pq;
    pq.push(Node(src, dist[src]));

    while(pq.size() != 0)
    {
        int u = pq.top().v;
        pq.pop();

        if(vis[u] == true) continue;

        vis[u] = true;

        for(int v = 1; v<=N; v++)
        {
            int cost = adj[u][v];
            if(cost != 0)
            {
                if(dist[u] + cost < dist[v])
                {
                    dist[v] = dist[u] + cost;
                    parent[v] = u;
                    pq.push(Node(v, dist[v]));
                }
            }
        }
    }
}

void input()
{
    cin >> N >> E;
    int id = 1;
    for(int i = 0; i<E; i++)
    {
        string s1, s2;
        int u, v, w;
        cin >> s1 >> s2 >> w;
        if(mark1[s1]==0)
        {
            mark1[s1] = id;
            mark2[id] = s1;
            id++;
        }
        if(mark1[s2]==0)
        {
            mark1[s2] = id;
            mark2[id] = s2;
            id++;
        }
        u = mark1[s1];
        v = mark1[s2];
        adj[u][v] = w;
        adj[v][u] = w;
    }
}


void PrintPath(int x)
{
    if(x == -1) return;
    PrintPath(parent[x]);
    cout << mark2[x] << " ";
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    init();
    input();

    dijstra(1);

    for(int i = 1; i<=N; ++i)
    {
        cout << "Node " << mark2[i] << ": " << endl;
        cout << "Path : ";
        PrintPath(i);
        cout << "Distance : " << dist[i] << endl;
        cout << endl;
        cout << endl;
    }
}



/*
input image: https://www.geeksforgeeks.org/wp-content/uploads/Fig-11.jpg

9 14
AA BB 4
AA HH 8
BB HH 11
BB CC 8
HH II 7
HH GG 1
CC II 2
II GG 6
CC DD 7
CC FF 4
GG FF 2
DD FF 14
DD EE 9
FF EE 10

*/