t.cpp

// Travel by Car

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <map>
#include <stdio.h>
#include <string.h>
#include <initializer_list>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <set>

using namespace std;

struct Edge {
    int to;
    int cost;
};

vector< vector <int> > graph;

vector<bool> visited;
//vector<int> distance;

int dijkstra(vector< vector<int> > graph, int N, int from, int to)
{
    vector<int> distance = vector<int>(graph.size(), 100000);
    distance[from] = 0;

    priority_queue<int> q;
    q.push(from);
    while (!q.empty()) {
        int p = q.top();
        q.pop();

        /*
        for (auto e = graph[p]; e != graph[p].end(); e++) {
            if (!visited[p] && distance[e->to] > (distance[p] + e->cost)) {
                distance[e->to] = distance[p] + e->cost;
            }
        }
        */

        for (int i = graph[p][0]; i < N; i++) {
            if (graph[p][i] == 100000) {
                continue;
            }
            if (!visited[p] && distance[i] > distance[p] + graph[p][i] ) {
                distance[i] = distance[p] + graph[p][i];
                q.push(i);
            }
        }
        if (p != 100000) {
            visited[p] = true;
        }
    }
    return distance[to];
}


int dp[303][303];

void WarshallFloyd(vector< vector <int> > graph, int N)
{
    //int dp[N][N];

    // init
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][j]) {
                dp[i][j] = graph[i][j];
            }
            else {
                dp[i][j] = 0;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N ; k++) {
            for (int j = 0; j < N ; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
}

int traverse(vector< vector <Edge> > graph, int from, int to, int cost)
{
    if (from == to) {
        return 0;
    }
    for (auto e = graph[from].begin(); e != graph[from].end(); e++) {
        cost = min(cost,traverse(graph,e->to,to,cost+e->cost));

    }
    visited[from] = true;
    return cost;
}

int main()
{
    int N, M, L;
    cin >> N >> M >> L;

    cout << "1";
    graph = vector<vector<int> >(N, vector<int>(N,100000));

    cout << "2";
    for (int i = 0; i < M; i++) {
        int from, to ,cost;
        cin >> from >> to >> cost;
        from--;
        to--;
        graph[from][to] = cost;
        graph[to][from] = cost;
    }
    cout << "3";

    int Q;
    cin >> Q;
    cout << "4" << Q;

    for (int i = 0; i < Q; i++) {
        int from, to;
        cin >> from >> to;
         from--;
         to--;
cout << "5";

        visited = vector<bool>(N,false);
        cout << "6";

        int cost = dijkstra(graph, N, from, to);
        cout << "7";

        WarshallFloyd(graph, N);

        cout << endl;
        cout << cost << endl;
    }

    return 0;
}