Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 此题神坑，先边数后点数一定要注意啊，附上JAVA版AC代码

Posted by WonderMouse at 2015-02-08 17:24:32 on Problem 2387
```import java.util.*;
public class POJ2387 {
public static class Pair implements Comparable<Pair>
{
int v,w;
Pair(int v,int weight)
{
this.v=v;w=weight;
}
public int compareTo(Pair x) {
return this.w-x.w;
}
}

public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int t=in.nextInt(),n=in.nextInt();
ArrayList<Pair>[] path=new ArrayList[n+1];
int[] d=new int[n+1];
for(int i=1;i<=n;i++)
{
path[i]=new ArrayList<Pair>();
d[i]=-1;
}
for(int i=0;i<t;i++)
{
int a=in.nextInt(),b=in.nextInt(),
c=in.nextInt();
}
Queue<Pair> q=new PriorityQueue<Pair>();
while(!q.isEmpty())
{
Pair a=q.poll();
while(!q.isEmpty()&&a.w>d[a.v])
a=q.poll();
for(int i=0;i<path[a.v].size();i++)
{
Pair b=path[a.v].get(i);
if(d[b.v]==-1||d[b.v]>d[a.v]+b.w)
{
d[b.v]=d[a.v]+b.w;
}
}
}
System.out.println(d[n]);
}
}```

Followed by: