一时兴起写了了个Java里的SPFA算法。。
。。C++0MSAC的题目我用Java要2000MS
不过我滥用了Java的特性。。类都开泛滥了。。一个SPFA开了五个类
题目是PKU 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)
{
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));
}
}
本高亮代码使用codeHl生成，
