Skip to content

Instantly share code, notes, and snippets.

@oskimura
Created November 8, 2019 03:13
Show Gist options
  • Save oskimura/248f9eab8257388311ff5a1d1afdc76f to your computer and use it in GitHub Desktop.
Save oskimura/248f9eab8257388311ff5a1d1afdc76f to your computer and use it in GitHub Desktop.
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment