#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510,M = 100010;
int h[N],w[M],e[M],ne[M];
bool st[N];
int idx,n,m;
int dist[N];
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra(){
dist[1] = 0;
for(int i = 0;i<n;i++){
int t = -1;
for(int j = 1;j<=n;j++){
if(!st[j] && (t == -1 || dist[j]<dist[t])){
t = j;
}
}
st[t] = true;
for(int i = h[t]; i!=-1; i = ne[i]){
int j = e[i];
dist[j] = min(dist[j], dist[t]+w[i]);
}
}
}
int main(){
cin>>n>>m;
memset(dist, 0x3f, sizeof dist);
memset(h, -1, sizeof h);
while(m--){
int a, b, c;
cin>>a>>b>>c;
add(a,b,c);
}
dijkstra();
if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了,则存在路径
cout << dist[n];
else
cout << "-1";
}
import java.util.*;
import java.io.*;
class Main{
static final int N = 510;
static final int M = 100005;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] w = new int[M];
static int[] ne = new int[M];
static int n, m,idx;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static class Pair{
int first;
int second;
Pair(int x, int y){
first = x;
second = y;
}
}
static void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
static void dijkstra(){
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
PriorityQueue<Pair> queue = new PriorityQueue<Pair>((a, b) -> Integer.compare(a.second, b.second));
queue.offer(new Pair(1, 0));
while (!queue.isEmpty()) {
Pair pair = queue.poll();
int node = pair.first;
int dis = pair.second;
if (st[node]) {
// 不再需要 continue,确保所有可达节点都被处理
continue;
}
st[node] = true;
for (int i = h[node]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[node] + w[i]) {
dist[j] = dist[node] + w[i];
queue.offer(new Pair(j, dist[j]));
}
}
}
}
public static void main(String[] args) throws IOException{
Arrays.fill(h, -1);
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer tokenizer = new StringTokenizer(read.readLine());
n = Integer.parseInt(tokenizer.nextToken());
m = Integer.parseInt(tokenizer.nextToken());
for(int i = 0; i<m; i++){
int a, b, c;
tokenizer = new StringTokenizer(read.readLine());
a = Integer.parseInt(tokenizer.nextToken());
b = Integer.parseInt(tokenizer.nextToken());
c = Integer.parseInt(tokenizer.nextToken());
add(a, b, c);
}
dijkstra();
if(dist[n] == Integer.MAX_VALUE){
writer.write(String.valueOf(-1));
}else{
writer.write(String.valueOf(dist[n]));
}
read.close();
writer.close();
}
}
邻接矩阵,适用于稠密图
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
int g[N][N], dist[N];
bool st[N];
int n, m;
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i<n; i++){
int t = -1;
for(int j = 1; j<=n; j++){
if(!st[j] && (t==-1 || dist[j]<dist[t])){
t = j;
}
}
st[t] = true;
for(int j = 1;j<=n; j++){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
cin>>n>>m;
memset(g, 0x3f, sizeof g);
while(m--){
int a, b, c;
cin>>a>>b>>c;
g[a][b] = min(g[a][b], c);
}
cout << dijkstra() << endl;
return 0;
}
spfa
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010;
int e[N],w[N], ne[N], h[N];
int dist[N];
int idx, n, m;
bool st[N];
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa(){
queue<int> q;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q.push(1);
st[1] = true;
while(q.size()){
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i!=-1; i = ne[i]){
int j = e[i];
if( dist[t]+w[i] < dist[j]){
dist[j] = dist[t]+w[i];
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main(){
memset(h, -1, sizeof h);
cin>>n>>m;
while(m--){
int a, b, c;
cin>>a>>b>>c;
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);
}
超级原点的单源最短路径
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的头文件
using namespace std;
typedef pair<int, int> PII;//堆里存储距离和节点编号
const int N = 300010;
int n, m, k, q;
int e[N], w[N], h[N],ne[N], dist[N];
bool st[N];
int idx;
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra(){
priority_queue<PII, vector<PII>, greater<PII>> q;
dist[0]=0; //超级源点的下标为0,从超级源点开始做单源最短路**
q.push({0,0});
while(q.size()){
auto t = q.top();
q.pop();
int distance = t.first;
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i!=-1; i = ne[i]){
int j = e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j] = dist[ver]+w[i];
q.push({dist[j], j});
}
}
}
}
int main(){
memset(h, -1, sizeof h);
memset(dist, 0x3f, sizeof dist);
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
cin>>k;
while(k--){//超级原点
int val;
cin>>val;
add(0, val , 0);
}
dijkstra();
cin>>q;
while(q--){
int val; cin>>val;
cout<<dist[val]<<endl;
}
}