傳送門：

P4779 【模板】單源最短路徑（標準版） - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)https://www.luogu.com.cn/problem/P4779

---

? ? ? ? 先給代碼：

import java.util.*; import java.io.*; class edge implements Comparable<edge>{int pos;int dis;public edge(int pos,int dis){this.pos=pos;this.dis=dis;}@Overridepublic int compareTo(edge o){return this.dis-o.dis;} } public class Main {static int n,m,s,cnt;static int[] vv,ww,nex,head;static edge[] e;public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer st = new StreamTokenizer(br);st.nextToken();n=(int)st.nval;st.nextToken();m=(int)st.nval;st.nextToken();s=(int)st.nval;vv=new int[m+1];ww=new int[m+1];head=new int[n+1];nex=new int[m+1];e=new edge[m+1];for(int i=1;i<=m;i++){st.nextToken();int u=(int)st.nval;st.nextToken();int v=(int)st.nval;st.nextToken();int w=(int)st.nval;add_edge(u,v,w);}int[] ans = dijkstra(s);for(int i=1;i<=n;i++){System.out.print(ans[i] + " ");}}static void add_edge(int u,int v,int w){vv[++cnt]=v;ww[cnt]=w;nex[cnt]=head[u];head[u]=cnt;}static int[] dijkstra(int start){boolean[] vis=new boolean[n+1];Arrays.fill(vis,false);Queue<edge> q = new PriorityQueue<>();q.offer(new edge(start,0));int[] dis=new int[n+1];Arrays.fill(dis,0x7fffffff);dis[start]=0;while(!q.isEmpty()){edge node = q.poll();int x=node.pos;if(vis[x]) continue;vis[x]=true;for(int i=head[x];i>0;i=nex[i]){int y=vv[i];if(dis[y]>dis[x]+ww[i]){dis[y]=dis[x]+ww[i];if(!vis[y])q.offer(new edge(y,dis[y]));}}}return dis;} }

? ? ? ? 這道題需要用到堆優(yōu)化，也就是優(yōu)先隊列，c++版的過程可以看這位大佬的dijkstra 詳解 - little_sun 的博客 - 洛谷博客 (luogu.com.cn)https://www.luogu.com.cn/blog/little-sun/dijkstra

? ? ? ? 建議懂了他的做法之后，再看我的代碼，會好理解一些。但是特別需要注意的是，c++可以用struct，但java不可以用class，為什么呢？因為java的類太笨了，做題要么超時，要么超內(nèi)存。

這時候我們可以為每一個變量定義一個數(shù)組，也是一樣的道理

vv=new int[m+1];ww=new int[m+1];head=new int[n+1];nex=new int[m+1];

? ? ? ? 這里給出弱化版?zhèn)魉烷T：(78條消息) p3371 單源最短路徑(弱化版)-java題解-最短路_17號列車的博客-CSDN博客https://blog.csdn.net/weixin_58428691/article/details/123998358?spm=1001.2014.3001.5502

總結

以上是生活随笔為你收集整理的p4779 单源最短路径(标准版)-java版的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。