0%

专题四 最短路练习

POJ 2387 Til the Cows Come Home

题目就是求$T$条双向边,$N$个顶点的单源最短路径$min(1,N)$

这题用$scanf$会快很多,但我没用它。

没有优化的$Dijkstra$算法:$Time:157ms$,$O(N^2)$

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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e3+10;
const int INF=0x3f3f3f3f;
int e[maxn][maxn];
int dis[maxn],vis[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T,N;
cin>>T>>N;
memset(e,INF,sizeof e);
while(T--){
int a,b,c;
cin>>a>>b>>c;
if(c<e[a][b]) e[a][b]=e[b][a]=c;
}

for(int i=1;i<=N;i++){
dis[i]=e[1][i];
}
memset(vis,0,sizeof vis);
dis[1]=0;
vis[1]=1;
int t=N-1;
while(t--){
int mi=INF,mi_idx;
for(int i=1;i<=N;i++){
if(!vis[i]&&dis[i]<mi){
mi=dis[i];
mi_idx=i;
}
}
vis[mi_idx]=1;
for(int i=1;i<=N;i++){
if(!vis[i]&&e[mi_idx][i]!=INF&&dis[i]>dis[mi_idx]+e[mi_idx][i]){
dis[i]=dis[mi_idx]+e[mi_idx][i];
}
}
}
cout<<dis[N];
return 0;
}

堆优化的$Dijkstra$算法:$Time:94ms$,$O(Elog_E)$

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
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e3+10;
struct node{
int v,c;
node(int _v=0,int _c=0):v(_v),c(_c){}
bool operator <(const node &x)const{
return c>x.c;
}
};
struct Edge{
int v,cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[maxn];
int vis[maxn],dis[maxn];
void addedge(int u,int v,int c){
E[u].push_back(Edge(v,c));
E[v].push_back(Edge(u,c));
}
void Dijkstra(int n,int start){
memset(vis,0,sizeof 0);
memset(dis,INF,sizeof dis);
dis[start]=0;
priority_queue<node>pq;
while(!pq.empty()) pq.pop();
pq.push(node(start,0));
node tmp;
while(!pq.empty()){
tmp=pq.top();
pq.pop();
int cur=tmp.v;
if(vis[cur]) continue;
vis[cur]=1;
for(int i=0;i<E[cur].size();i++){
int v=E[cur][i].v;
int cost=E[cur][i].cost;
if(!vis[v]&&dis[v]>dis[cur]+cost){
dis[v]=dis[cur]+cost;
pq.push(node(v,dis[v]));
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T,N;
cin>>T>>N;
while(T--){
int u,v,c;
cin>>u>>v>>c;
//在这里用优先队列加vis数组标记,所以不用考虑重边
addedge(u,v,c);
}
Dijkstra(N,1);
cout<<dis[N];
return 0;
}

用spfa会更快,有时间看一下。

POJ 2253 Frogger

POJ 1797 Heavy Transportation

POJ 3268 Silver Cow Party

POJ 1860 Currency Exchange

POJ 3259 Wormholes

POJ 1502 MPI Maelstrom

POJ 3660 Cow Contest

POJ 2240 Arbitrage

POJ 1511 Invitation Cards

POJ 3159 Candies

POJ 2502 Subway

POJ 1062 昂贵的聘礼

POJ 1847 Tram

LightOJ 1074 Extended Traffic

HDU 4725 The Shortest Path in Nya Graph

HDU 3416 Marriage Match IV

HDU 4370 0 or 1

POJ 3169 Layout

如果对您有帮助,请我喝杯奶茶?