最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 24512 Accepted Submission(s): 10549
Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0
Sample Output
3 2
Source
Recommend
闲的蛋疼，
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100 + 5
#define MAXM 20000 + 5
int n, m;
int d[MAXN], h[MAXN], cnt;
struct node{
int u, w;
bool operator < (const node &rhs)const{
return w > rhs.w;
}
};
struct edge{
int v, w, nxt;
}e[MAXM];
void add(int u, int v, int w){
e[cnt]=(edge){v, w, h[u]};
h[u]=cnt++;
e[cnt]=(edge){u, w, h[v]};
h[v]=cnt++;
}
#define INF (1<<30)
bool done[MAXN];
int dijkstra(int s, int t){
fill_n(d+1, n, INF); d[1]=0;
fill_n(done+1, n, false);
priority_queue<node> q;
q.push((node){1, d[1]});
while(!q.empty()){
node tu = q.top(); q.pop();
int u = tu.u, i;
if(done[u]) continue; done[u]=true;
if(u==t) return d[t];
for(i=h[u]; i!=-1; i=e[i].nxt){
int v = e[i].v, w = e[i].w;
if(d[v] > d[u] + w){
d[v] = d[u] + w;
q.push((node){v, d[v]});
}
}
}
return d[t];
}
int main(){
while(scanf(" %d %d", &n, &m)==2 && (n|m)){
int i, j;
cnt = 0; fill_n(h+1, n, -1);
for(i=0; i<m; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
}
printf("%d
", dijkstra(1, n));
}
return 0;
}
java :
import java.awt.Point;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
class MyComp implements Comparator<Point>{
@Override
public int compare(Point o1, Point o2) {
// TODO Auto-generated method stub
if(o1.y==o2.y) return 0;
return o1.y<o2.y ? -1 : 1;
}
}
class Dijkstra{
static final int MAXN=111,
MAXM=22222;
static final int INF = 10000000;
final int s, t;
boolean[] vis = new boolean[MAXN];
static int[] dis = new int[MAXN];
static int counter=0;
int[] w = new int[MAXM],
next = new int[MAXM],
to = new int[MAXM];
int[] h = new int[MAXN];
static PriorityQueue<Point> q=new PriorityQueue<Point>(10,
new MyComp());
public Dijkstra(int s, int t){
this.s=s; this.t=t;
counter=0;
for(int i=1; i<=t; i++) h[i]=-1;
}
private void ini(){
for(int i=s; i<=t; i++){
dis[i]=INF; vis[i]=false;
}
q.clear(); dis[s]=0;
}
public void add(int u, int v, int _w){
w[counter]=_w; next[counter]=h[u];
to[counter]=v; h[u]=counter++;
w[counter]=_w; next[counter]=h[v];
to[counter]=u; h[v]=counter++;
}
public int run(){
ini(); q.add(new Point(s,0));
while(!q.isEmpty()){
Point np = new Point(q.poll());
if(np.x == t) return dis[t];
if(vis[np.x]) continue; vis[np.x]=true;
for(int i=h[np.x]; i!=-1; i=next[i]){
int v = to[i], tw = w[i];
if(dis[np.x]+tw<dis[v]){
dis[v] = dis[np.x] + tw;
q.add(new Point(v,dis[v]));
}
}
}
return dis[t];
}
}
public class Main {
public static void main(String[] args){
// TODO Auto-generated method stub
// File f = new File("F:\pro\javaPro\hdu\hdu2544");
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt(), m=sc.nextInt();
if(n==0 && m==0) break;
Dijkstra dij = new Dijkstra(1, n);
for(int i=0; i<m; i++)
dij.add(sc.nextInt(), sc.nextInt(), sc.nextInt());
System.out.println(dij.run());
}
}
}