這題基本上忘記dijkstra應該就不知道怎麼就不知道怎麼做了哈哈
我特地回去重新複習了一下
然後以n為起點, 去紀錄每個到n的距離, 接著在記錄所有路線的可能, 但我不知道我的方法出錯在哪邊, 會tle
class Solution {
public:
int findMinDistVertex(const vector<int> &dist, const vector<bool> visited) {
int minDist = INT_MAX;
int minVertex = -1;
for (int i = 0; i < dist.size(); i++) {
if (dist[i] < minDist && !visited[i]) {
minDist = dist[i];
minVertex = i;
}
}
return minVertex;
}vector<int> dijkstra(vector<vector<int>> graph, int src) {
int n = graph.size();
// cout << n << "\n";
vector<int> dist(n, INT_MAX);
vector<bool> visited(n, false);
dist[src] = 0;
for (int count = 0; count < n; count++) {
int u = findMinDistVertex(dist, visited);
if (u < 0)
break;
// cout << u << "!\n";
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}int countRestrictedPaths(int n, vector<vector<int>> &edges) {
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
for (auto e : edges) {
graph[e[0]][e[1]] = e[2];
graph[e[1]][e[0]] = e[2];
}
vector<int> dist = dijkstra(graph, n);
vector<bool> visited(n + 1, false);
queue<int> q;
vector<int> dp(n + 1, 0);
dp[n] = 1;
long m = 1e9 + 7;
for (int i = 0; i < dist.size(); i++) {
int u = findMinDistVertex(dist, visited);
if (u < 0) {
break;
}
visited[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] && !visited[v] && dist[u] < dist[v]) {
dp[v] = dp[u] + dp[v];
dp[v] %= m;
}
}
}
return dp[1];
}
};
我猜是因為我在找最短距離找一個array, 我看討論區看到比較常用的做法應該都會是priority_queue, 這樣抓點只需要O(1)的時間
哇, 到這邊已經有點心力交瘁了XD
class Solution {
public:
int countRestrictedPaths(int n, vector<vector<int>> &edges) {
unordered_map<int, vector<pair<int, int>>> gp;
for (auto &edge : edges) {
gp[edge[0]].push_back({edge[1], edge[2]});
gp[edge[1]].push_back({edge[0], edge[2]});
}vector<int> dist(n + 1, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
pq;
pq.push({0, n});
dist[n] = 0;int u, v, w;
while (!pq.empty()) {
pair<int, int> p = pq.top();
pq.pop();
u = p.second;
for (auto &to : gp[u]) {
v = to.first, w = to.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
vector<int> dp(n + 1, -1);
return dfs(gp, n, dp, dist);
}int dfs(unordered_map<int, vector<pair<int, int>>> &gp, int s,
vector<int> &dp, vector<int> &dist) {
int mod = 1e9 + 7;
if (s == 1)
return 1;
if (dp[s] != -1)
return dp[s];
int sum = 0, weight, val;
for (auto &n : gp[s]) {
weight = dist[s];
val = dist[n.first];
if (val > weight) {
sum = (sum % mod + dfs(gp, n.first, dp, dist) % mod) % mod;
}
}
return dp[s] = sum % mod;
}
};
這是我覺得比較好的解答, 蓋唸上雷同但他在很多處理都換比較高效率的方法, 像上面提到的priority_queue, 以及unordered_map做dfs等等
這就難在實作吧哈哈, 這題估計當下給我時間我也做不太出來
