目录
题目：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1
朴素版dijkstra算法 —— 稠密图用邻接矩阵存
模板：
dist[i]存从点1到i的最短距离 初始化dist[1]=0
循环n次（更新n个点）
{
每次从1~n点中寻找一个未更新且距离起点最近的点
标记该点
用该点更新到其他点的最短距离
}public static int dijkstra() { Arrays.fill(dist,0x3f3f3f3f); dist[1]=0; for(int i=0;i<n;i++) //n次循环 { int t=-1; //先找出未标记的点中 距离起点最近的点 for(int j=1;j<=n;j++) if(st[j]==0&&(t==-1||dist[j]<dist[t])) t=j; st[t]=1; //用t更新到其他点的最短距离 for(int j=1;j<=n;j++) dist[j]=Math.min(dist[j],dist[t]+g[t][j]); } return dist[n]; }
/*
*道阻且长，行则将至*
author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;
class Main
{
static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N=510;
static int n,m;
static int[][] g=new int[N][N];
static int[] dist=new int[N];
static int[] st=new int[N];
public static int dijkstra()
{
Arrays.fill(dist,0x3f3f3f3f);
dist[1]=0;
for(int i=0;i<n;i++) //n次循环
{
int t=-1;
//先找出未标记的点中 距离起点最近的点
for(int j=1;j<=n;j++)
if(st[j]==0&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=1;
//用t更新到其他点的最短距离
for(int j=1;j<=n;j++) dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
}
return dist[n];
}
public static void main(String[] args) throws IOException
{
n=rd.nextInt();
m=rd.nextInt();
for(int i=1;i<=n;i++)
Arrays.fill(g[i],0x3f3f3f3f);
while(m-->0)
{
int a=rd.nextInt(),b=rd.nextInt(),c=rd.nextInt();
g[a][b]=Math.min(g[a][b],c); //如果有重边，则取最小的那个边
}
int t=dijkstra();
if(t==0x3f3f3f3f) wt.print(-1);
else wt.print(t);
wt.flush();
}
static class rd
{
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tk=new StringTokenizer("");
static String nextLine() throws IOException
{
return bf.readLine();
}
static String next() throws IOException
{
while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());
return tk.nextToken();
}
static int nextInt() throws IOException
{
return Integer.parseInt(next());
}
static double nextDouble() throws IOException
{
return Double.parseDouble(next());
}
static long nextLong() throws IOException
{
return Long.parseLong(next());
}
static BigInteger nextBig() throws IOException
{
BigInteger d=new BigInteger(rd.nextLine());
return d;
}
}
}
class PII
{
int x,y;
PII(int x,int y)
{
this.x=x;
this.y=y;
}
}堆优化版dijkstra算法 —— 稀疏图用邻接表存
堆优化版dijkstra适合稀疏图
堆优化和朴素版思路一样：
- 小顶堆每次取距离起点最近的点
- 若未标记，则用该点更新到其他点的最短距离
/*
*道阻且长，行则将至*
author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;
class Main
{
static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N=150100;
static int n,m,idx;
static int[] h=new int[N],e=new int[N],ne=new int[N],w=new int[N];
static int[] dist=new int[N];
static int[] st=new int[N];
public static void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
public static int dijkstra()
{
Arrays.fill(dist,0x3f3f3f3f);
dist[1]=0;
PriorityQueue<PII> q=new PriorityQueue<>();
q.offer(new PII(0,1)); //按first排序 所以距离放前边
while(!q.isEmpty())
{
var t=q.poll();
int p=t.y;
int d=t.x;
if(st[p]==1) continue;
st[p]=1;
for(int i=h[p];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>d+w[i])
{
dist[j]=d+w[i];
q.offer(new PII(dist[j],j));
}
}
}
return dist[n];
}
public static void main(String[] args) throws IOException
{
n=rd.nextInt();
m=rd.nextInt();
Arrays.fill(h,-1);
while(m-->0)
{
int a=rd.nextInt(),b=rd.nextInt(),c=rd.nextInt();
add(a,b,c); //如果有重边，则取最小的那个边
}
int t=dijkstra();
if(t==0x3f3f3f3f) wt.print(-1);
else wt.print(t);
wt.flush();
}
static class rd
{
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tk=new StringTokenizer("");
static String nextLine() throws IOException
{
return bf.readLine();
}
static String next() throws IOException
{
while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());
return tk.nextToken();
}
static int nextInt() throws IOException
{
return Integer.parseInt(next());
}
static double nextDouble() throws IOException
{
return Double.parseDouble(next());
}
static long nextLong() throws IOException
{
return Long.parseLong(next());
}
static BigInteger nextBig() throws IOException
{
BigInteger d=new BigInteger(rd.nextLine());
return d;
}
}
}
class PII implements Comparable<PII>
{
public int x;
public int y;
public PII(int x,int y)
{
this.x=x;
this.y=y;
}
public int compareTo(PII o)
{
return Integer.compare(x,o.x);
}
}1488. 最短距离 – 超级源点
题目：
n个村庄有m条无向道路，每条道路长c
有k个村庄有商店
给q个询问，输出qi点到商店的最近距离
思路：
设置了一个超级源点，该源点到每个商店的距离都是0
因此从这个点就可以代表所有的商店，只需要计算当前点到这个超级源点的最短路即可
1、dijkstra算法
/*
*道阻且长，行则将至*
author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;
class Main
{
static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N=2000000,M=2*N;
static int n,m,idx;
static int[] h=new int[N],e=new int[N],ne=new int[N],w=new int[N];
static int[] dist=new int[N];
static int[] st=new int[N];
public static void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
public static void dijkstra()
{
Arrays.fill(dist,0x3f3f3f3f);
PriorityQueue<PII> q=new PriorityQueue<>();
q.offer(new PII(0,0));
dist[0]=0;
while(!q.isEmpty())
{
var t=q.poll();
int ver=t.y;
int d=t.x;
if(st[ver]==1) continue;
st[ver]=1;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>d+w[i])
{
dist[j]=d+w[i];
q.offer(new PII(dist[j],j));
}
}
}
}
public static void main(String[] args) throws IOException
{
n=rd.nextInt();
m=rd.nextInt();
Arrays.fill(h,-1);
while(m-->0)
{
int a=rd.nextInt(),b=rd.nextInt(),c=rd.nextInt();
add(a,b,c);
add(b,a,c);
}
int k=rd.nextInt();
while(k-->0)
{
int x=rd.nextInt();
add(0,x,0); //设置一个超级源点，每个商店到这个源点距离均为0
//即超级源点代表所有商店，因此只要计算每个询问到超级源点的最短距离即可
}
dijkstra();
int que=rd.nextInt();
while(que-->0)
{
int qq=rd.nextInt();
wt.println(dist[qq]);
}
wt.flush();
}
static class rd
{
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tk=new StringTokenizer("");
static String nextLine() throws IOException
{
return bf.readLine();
}
static String next() throws IOException
{
while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());
return tk.nextToken();
}
static int nextInt() throws IOException
{
return Integer.parseInt(next());
}
static double nextDouble() throws IOException
{
return Double.parseDouble(next());
}
static long nextLong() throws IOException
{
return Long.parseLong(next());
}
static BigInteger nextBig() throws IOException
{
BigInteger d=new BigInteger(rd.nextLine());
return d;
}
}
}
class PII implements Comparable<PII>
{
public int x;
public int y;
public PII(int x,int y)
{
this.x=x;
this.y=y;
}
public int compareTo(PII o)
{
return Integer.compare(x,o.x);
}
}2、spfa算法
/*
*道阻且长，行则将至*
author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;
class Main
{
static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N=2000000,M=2*N;
static int n,m,idx;
static int[] h=new int[N],e=new int[N],ne=new int[N],w=new int[N];
static int[] dist=new int[N];
static int[] st=new int[N];
public static void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
public static void spfa()
{
Queue<Integer> q=new LinkedList<>();
Arrays.fill(dist,0x3f3f3f3f);
q.offer(0);
st[0]=1;
dist[0]=0;
while(!q.isEmpty())
{
var t=q.poll();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(st[j]==0)
{
q.offer(j);
st[j]=1;
}
}
}
}
}
public static void main(String[] args) throws IOException
{
n=rd.nextInt();
m=rd.nextInt();
Arrays.fill(h,-1);
while(m-->0)
{
int a=rd.nextInt(),b=rd.nextInt(),c=rd.nextInt();
add(a,b,c);
add(b,a,c);
}
int k=rd.nextInt();
while(k-->0)
{
int x=rd.nextInt();
add(0,x,0); //设置一个超级源点，每个商店到这个源点距离均为0
//即超级源点代表所有商店，因此只要计算每个询问到超级源点的最短距离即可
}
spfa();
int que=rd.nextInt();
while(que-->0)
{
int qq=rd.nextInt();
wt.println(dist[qq]);
}
wt.flush();
}
static class rd
{
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tk=new StringTokenizer("");
static String nextLine() throws IOException
{
return bf.readLine();
}
static String next() throws IOException
{
while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());
return tk.nextToken();
}
static int nextInt() throws IOException
{
return Integer.parseInt(next());
}
static double nextDouble() throws IOException
{
return Double.parseDouble(next());
}
static long nextLong() throws IOException
{
return Long.parseLong(next());
}
static BigInteger nextBig() throws IOException
{
BigInteger d=new BigInteger(rd.nextLine());
return d;
}
}
}
class PII implements Comparable<PII>
{
public int x;
public int y;
public PII(int x,int y)
{
this.x=x;
this.y=y;
}
public int compareTo(PII o)
{
return Integer.compare(x,o.x);
}
}