\u4e00\u65f6\u5174\u8d77\u5199\u4e86\u4e86\u4e2aJava\u91cc\u7684SPFA\u7b97\u6cd5\u3002\u3002![](\"http:\/\/wjmzbmr.com\/wp-content\/uploads\/pic\/other_site\/img_baidu_j_0012.gif\")
\u3002\u3002C++0MSAC\u7684\u9898\u76ee\u6211\u7528Java\u89812000MS
\u4e0d\u8fc7\u6211\u6ee5\u7528\u4e86Java\u7684\u7279\u6027\u3002\u3002\u7c7b\u90fd\u5f00\u6cdb\u6ee5\u4e86\u3002\u3002\u4e00\u4e2aSPFA\u5f00\u4e86\u4e94\u4e2a\u7c7b![](\"http:\/\/wjmzbmr.com\/wp-content\/uploads\/pic\/other_site\/img_baidu_j_0007.gif\")
\u9898\u76ee\u662fPKU 2387![](\"http:\/\/wjmzbmr.com\/wp-content\/uploads\/pic\/other_site\/img_baidu_j_0003.gif\")
<\/p>\n
import java.util.*; \u4e00\u65f6\u5174\u8d77\u5199\u4e86\u4e86\u4e2aJava\u91cc\u7684SPFA\u7b97\u6cd5\u3002\u3002\u3002\u3002C++0MSAC\u7684\u9898\u76ee\u6211\u7528Java\u89812000MS\u4e0d\u8fc7\u6211\u6ee5\u7528\u4e86Java\u7684\u7279\u6027\u3002\u3002\u7c7b\u90fd\u5f00\u6cdb\u6ee5\u4e86\u3002\u3002\u4e00\u4e2aSPFA\u5f00\u4e86\u4e94\u4e2a\u7c7b\u9898\u76ee\u662fPKU 2387 import java.util.*;class Edge{ int t,c; Edge(int _t,int _c) {t=_t;c=_c;}}class Graph{ int n; List< List<Edge> > E; Graph(int _n) { n=_n; E=new ArrayList< List<Edge> >(n); for(int i=0;i<n;i++) E.add(new ArrayList<Edge>()); } void addEdge(int s,int t,int c) { E.get(s).add(new Edge(t,c)); E.get(t).add(new Edge(s,c)); } Iterator<Edge> adj(int v) {return E.get(v).iterator();}}class MyQueue extends ArrayDeque<Integer>{ int n;boolean[] inQ; MyQueue(int _n) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/117"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=117"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/117\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
class Edge
{
int t,c;
Edge(int _t,int _c)
{t=_t;c=_c;}
}
class Graph
{
int n;
List< List<Edge> > E;
Graph(int _n)
{
n=_n;
E=new ArrayList< List<Edge> >(n);
for(int i=0;i<n;i++) E.add(new ArrayList<Edge>());
}
void addEdge(int s,int t,int c)
{
E.get(s).add(new Edge(t,c));
E.get(t).add(new Edge(s,c));
}
Iterator<Edge> adj(int v)
{return E.get(v).iterator();}
}
class MyQueue extends ArrayDeque<Integer>
{
int n;boolean[] inQ;
MyQueue(int _n)
{
n=_n;
inQ=new boolean[n];
}
void put(int x)
{
if(!inQ[x])
{
super.add(x);
inQ[x]=true;
}
}
int get()
{
int t=super.poll();
inQ[t]=false;
return t;
}
}
class Spfa
{
final int inf=1<<29;
Graph G;
int[] dist;
MyQueue Q;
Spfa(Graph _G,int vs)
{
G=_G;
dist=new int[G.n];Arrays.fill(dist,inf);Q=new MyQueue(G.n);
dist[vs]=0;Q.put(vs);
while(!Q.isEmpty())
{
int t=Q.get();int cost=dist[t];
Iterator<Edge> i=G.adj(t);
while(i.hasNext())
{
Edge e=i.next();
int ncost=cost+e.c;
if(ncost<dist[e.t])
{
dist[e.t]=ncost;
Q.put(e.t);
}
}
}
}
int distTo(int v)
{
return dist[v];
}
}
public class Main
{
static Scanner in=new Scanner(System.in);
static public void main(String[] args)
{
int m=in.nextInt(),n=in.nextInt();
Graph G=new Graph(n);int s,t,c;
for(int i=0;i<m;i++)
{
s=in.nextInt();
t=in.nextInt();
c=in.nextInt();
G.addEdge(s-1,t-1,c);
}
Spfa solve=new Spfa(G,0);
System.out.println(solve.distTo(n-1));
}
}<\/em>
\u672c\u9ad8\u4eae\u4ee3\u7801\u4f7f\u7528codeHl\u751f\u6210\uff0c <\/p>\n","protected":false},"excerpt":{"rendered":"