#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string> #include<queue> #include<vector> using namespace std; struct Edge { int y; int weight; }; struct Node { int x; int weight; }; bool operator <(Node l, Node r) { return l.weight > r.weight; } vector<Edge>graph[1000]; int distra(int s, int t,int n) { int dist[1000]; bool isvisited[1000]; for (int i = 0; i < n; i++) { dist[i] = 1e9; isvisited[i] = false; } priority_queue<Node>queue; dist[s] = 0; Node node; node.x = s; node.weight = dist[s]; queue.push(node); while (!queue.empty()) { int x = queue.top().x; queue.pop(); if (isvisited[x]) { continue; } isvisited[x] = true; for (int i = 0; i < graph[x].size(); i++) { int y = graph[x][i].y; int weight = graph[x][i].weight; if (dist[y] > dist[x] + weight) { dist[y] = dist[x] + weight; node.x = y; node.weight = dist[y]; queue.push(node); } } } return dist[t]; } int main() { int n,m, k; while (cin >> n >> m >> k) { for (int i = 0; i < n; i++) { graph[i].clear(); } for (int i = 0; i < m; i++) { Edge e; int x; cin >> x >> e.y >> e.weight; graph[x].push_back(e); } for (int i = 0; i < k; i++) { int s, t; cin >> s >> t; int num = distra(s, t, n); cout << num << endl; } } return 0; } |
Double click to view unformatted code.