日志
有一个 n个点m𝑛𝑛个点 𝑚条边的无向图，请求出从 𝑠s到 t 𝑡的最短路长度。
#include <bits/stdc++.h>
using namespace std;
int numNodes, numEdges, sourceNode, targetNode;
vector<bool> visited(1000000, false);
struct Edge {
int to, weight, next = -1;
} graph[1000000];
vector<int> head(1000000, -1), distanceTo(1000000, INT_MAX);
int edgeCount = 0;
void addEdge(int from, int to, int weight) {
graph[edgeCount].to = to;
graph[edgeCount].weight = weight;
graph[edgeCount].next = head[from];
head[from] = edgeCount++;
}
struct Node {
int position, distance;
Node(int pos, int dist) : position(pos), distance(dist) {}
bool operator<(const Node& other) const {
return this->distance > other.distance;
}
};
priority_queue<Node> priorityQueue;
void dijkstra() {
distanceTo[sourceNode] = 0;
priorityQueue.push(Node(sourceNode, 0));
while (!priorityQueue.empty()) {
int currentNode = priorityQueue.top().position;
priorityQueue.pop();
if (!visited[currentNode]) {
visited[currentNode] = true;
for (int i = head[currentNode]; i != -1; i = graph[i].next) {
int neighbor = graph[i].to;
if (distanceTo[neighbor] > graph[i].weight + distanceTo[currentNode]) {
distanceTo[neighbor] = graph[i].weight + distanceTo[currentNode];
if (!visited[neighbor]) {
priorityQueue.push(Node(neighbor, distanceTo[neighbor]));
}
}
}
}
}
}
int main() {
cin >> numNodes >> numEdges >> sourceNode >> targetNode;
for (int i = 0; i < numEdges; i++) {
int from, to, weight;
cin >> from >> to >> weight;
addEdge(from, to, weight);
addEdge(to, from, weight);
}
dijkstra();
cout << distanceTo[targetNode];
return 0;
}
