POJ 2387 Til the Cows Come Home

本文最后更新于:2020年6月10日 下午

【POJ】2387 Til the Cows Come Home

题目链接:poj-2387


Dscription

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John’s field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.


Input

* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.


Output

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.


Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

Sample Output

90

Hint

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.


题目理解

​ 给定多个点以及部分点与点之间道路的过程,问从点1到点N的最短距离,保证1N之间有一条通路。

​ Dijkstra最短路问题,需要注意的是,本题可能多次输入两个点之间的距离,输入过程需要判断。


代码1 Dijkstra

#include<iostream>
#include<cstring> 
using namespace std;

const int INF = 0x3f3f3f3f;	//定义距离的最大值 
const int MAXN = 1005;
int mp[MAXN][MAXN];	//记录两点之间的距离 
int dis[MAXN];	//记录源点与其他点的距离 
bool vis[MAXN];	//访问记录 
int T, N;

void Dijkstra(int s, int e){	//接受起始点和终点 
	memset(vis, false, sizeof(vis));
	memset(dis, INF, sizeof(dis));
	dis[s] = 0;
	for(int i = 1; i <= N; ++i){
		int tmp = INF, k = -1;
		for(int j = 1; j <= N; ++j){	//找出未访问的点中与源点距离最小的点作为新的起始点 
			if(!vis[j] && dis[j] < tmp){
				k = j;
				tmp = dis[j];
			}
		}
		vis[k] = true;
		if(k == e){
			return;
		}
		for(int j = 1; j <= N; ++j){	//更新与上一个循环中找出的起始点相连的点与源点的距离 
			if(!vis[j]){
				dis[j] = min(dis[k] + mp[k][j], dis[j]);
			}
		}
	}
}


int main(){
	while(cin >> T >> N){
		memset(mp, INF, sizeof(mp));
		int p1, p2, d;
		for(int i = 0; i < T; ++i){
			cin >> p1 >> p2 >> d;
			if(mp[p1][p2] > d){	//当重复输入两个点的距离时,判定更新 
				mp[p1][p2] = d;
				mp[p2][p1] = d;
			}
		}
		Dijkstra(1, N);
		cout << dis[N] << endl;
	}
	
	return 0;
}

代码2 堆优化

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
int mp[MAXN][MAXN];
bool vis[MAXN];
int dis[MAXN]; 
int T, N;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

void Dijkstra(int s){
	memset(vis, false, sizeof(vis));
	memset(dis, INF, sizeof(dis));
	dis[s] = 0;
	q.push(make_pair(0, s));
	while(!q.empty()){	//BFS思路 
		pair<int, int> p;
		p = q.top();
		q.pop();
		if(vis[p.second])
			continue;
		vis[p.second] = true;
		for(int i = 1; i <= N; ++i){
			if(!vis[i] && dis[i] > dis[p.second] + mp[p.second][i]){
				dis[i] = dis[p.second] + mp[p.second][i];
				q.push(make_pair(dis[i], i));
			}
		}
	}
}

int main(){
	while(cin >> T >> N){
		memset(mp, INF, sizeof(mp));
		for(int i = 0; i < T; ++i){
			int p1, p2, d;
			cin >> p1 >> p2 >> d;
			if(mp[p1][p2] > d){
				mp[p1][p2] = d;
				mp[p2][p1] = d;
			}
		}
		Dijkstra(1);
		cout << dis[N] << endl;
	} 
	
	return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!