【HDU-2544】解题报告（最短路，dij）

原始题目

最短路

  • Time Limit: 5000/1000 MS (Java/Others)
  • Memory Limit: 32768/32768 K (Java/Others)
  • Total Submission(s): 88011
  • Accepted Submission(s): 38096

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

UESTC 6th Programming Contest Online

Recommend

lcy

题目大意

如题

解题思路

  • 单源正权，Dijkstra最短路模板题

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <bits/stdc++.h> 
using namespace std;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define np next_permutation
#define ms(x,a) memset((x),(a),sizeof(x))
//优先队列迪杰斯特拉 
const int maxn=1e5+5;
struct Edge{
	int u,v,w;
	Edge(int _u,int _v,int _w):u(_u),v(_v),w(_w){
	};
};
vector <Edge> edges[maxn];

int dis[maxn];
bool vis[maxn];
int n,m,uu,vv,ww;

void init(int n){ //n个结点的边集都清空 
	rep(i,0,maxn){
		edges[i].clear();
	}
}

void addEdge(int u,int v,int w){
	edges[u].pb(Edge(u,v,w));
}

struct Node{
	int Id,W;
	Node(int _Id,int _W):Id(_Id),W(_W){
	};
	bool operator < (const Node &b) const {W>b.W;}
};

void Dijkstra(int s){
	ms(vis,0);
	ms(dis,INF);
	priority_queue <Node> q;
	q.push(Node(s,0)) ,dis[s]=0;
	while(!q.empty()){
		Node now=q.top();
		q.pop();
		int index=now.Id;
		if(dis[index]!=now.W) continue;
		rep(i,0,edges[index].size()){
			if(dis[edges[index][i].v]>dis[index]+edges[index][i].w){
				dis[edges[index][i].v]=dis[index]+edges[index][i].w;
				q.push(Node(edges[index][i].v,dis[edges[index][i].v]));
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);

	while(cin>>n>>m&&n+m){
		init(n);
		rep(i,1,m+1){
			cin>>uu>>vv>>ww;
			addEdge(uu,vv,ww);
			addEdge(vv,uu,ww);
		} 
		Dijkstra(1);
		cout<<dis[n]<<endl; 
	} 
}

收获与反思

  • 理解熟悉模板