日志

有一个 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;

}