# Poj Solution 2387

```http://poj.org/problem?id=2387

import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int c=0;
int t=in.nextInt();//����˳�����WA��N�Σ������������⣡
int n=in.nextInt();
int dist[]=new int[n+1];//��������ȷ�������С������RE��N�Σ�
int[][] w=new int[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
w[i][j]=Integer.MAX_VALUE;
}
}
for(int i=0;i< t;i++){//����}�㼰֮�����
int sn=in.nextInt();
int en=in.nextInt();
c=in.nextInt();
if(c< w[sn][en])
w[sn][en]=w[en][sn]=c;
}
dijkstra(n,w,dist);
System.out.println(dist[1]);
}

public static void dijkstra(int v ,int[][] a, int[] dist){//���·��dijkstra�㷨
int nn = dist.length - 1 ;
boolean[] s = new boolean[nn+1];
//��ʼ��
for(int i = 1; i <= nn; i++)
dist[i] = a[v][i];
dist[v] = 0;
s[v] = true;
for(int i = 1; i < nn; i++){
int temp =Integer.MAX_VALUE;
int u = v;
for(int j = 1; j < nn; j++){
if(!s[j] && dist[j] < temp&&dist[j]>0){
u = j;
temp = dist[j];
}
}
s[u] = true;  //�ҵ��˵�һ����S�Ľڵ�
for(int j = 1; j <= nn; j++)
if(!s[j] &&dist[u]+a[u][j]< dist[j]&& a[u][j] < Integer.MAX_VALUE)
dist[j] =dist[u]+a[u][j];
}
}
}

```
This entry was posted in poj. Bookmark the permalink.