資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：判斷從特定城市出發是否可以進行環形旅行
假設有n個城市和m條連線它們的道路。每條道路都是單向的，從起點城市到終點城市需要特定時間。道路資訊儲存在陣列roads中，每個元素的格式為(起點城市，終點城市，時間)。現在，一個人從一個城市到另一個城市旅行，並且旅行必須是環形旅行。當一個人從特定城市出發，經過一條或多條道路，最終回到同一城市時，該旅行可以被稱為環形旅行。因此，對於每個城市，我們必須確定從該特定城市出發是否可以進行環形旅行。如果可以，則列印執行環形旅行所需的時間，否則列印-1。
例如，如果輸入為n = 4，m = 4，roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}，則輸出為：26 26 26 26。從每個城市出發，執行環形旅行都需要26個時間單位。
為了解決這個問題，我們將遵循以下步驟：
Define one 2D array graph(n) of pairs
for initialize i := 0, when i < m, update (increase i by 1), do:
x := first value of roads[i]
y := second value of roads[i]
z := third value of roads[i]
decrease x and y by 1
insert pair (y, z) at the end of graph[x]
for initialize i := 0, when i < n, update (increase i by 1), do:
q := a new priority queue
Define an array dst
insert pair (0, i) at the top of q
while size of q is non-zero, do:
pair p := top value of q
delete the top element from q
dt := first value of p
curr := second value of p
if dst[curr] is same as 0, then:
dst[curr] := dt
Come out from the loop
if dst[curr] is not equal to -1, then:
Ignore following part, skip to the next iteration
dst[curr] := dt
for element next in graph[curr], do:
tp := first value of next
cst := second value of next
insert pair(dt + cst, tp) at the top of q
if dst[i] is same as 0, then:
dst[i] := -1
print(dst[i])示例
讓我們看看以下實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int modval = (int) 1e9 + 7;
#define N 100
void solve(int n, int m, vector<tuple<int, int, int>> roads ) {
vector<vector<pair<int, int>>> graph(n);
for(int i = 0; i < m; i++) {
int x, y, z;
tie(x, y, z) = roads[i];
x--; y--;
graph[x].emplace_back(y, z);
}
for(int i = 0; i < n; i++) {
priority_queue<pair<int, int>> q;
vector<int> dst(n, -1);
q.emplace(0, i);
while(q.size()){
pair<int, int> p = q.top();
q.pop();
int curr, dt;
tie(dt, curr) = p;
if(dst[curr] == 0) {
dst[curr] = dt;
break;
}
if(dst[curr] != -1)
continue;
dst[curr] = dt;
for(auto next : graph[curr]){
int tp, cst;
tie(tp, cst) = next;
q.emplace(dt + cst, tp);
}
}
if(dst[i] == 0)
dst[i] = -1;
cout<< dst[i]<< endl;
}
}
int main() {
int n = 4, m = 4;
vector<tuple<int, int, int>> roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}};
solve(n, m, roads);
return 0;
}輸入
4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}
輸出
26 26 26 26
更新於： 2022年2月25日
455 次瀏覽
廣告