Description 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. OutputLine 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. 問題概述 第一行輸入T，N接下來的T行輸入點v，u以及邊長v，u的權重。N代表有1~N個點。 求母牛從N走到1的最短路徑。 問題分析 采用Dijstra算法，注意輸入的數據中可能會有相同的邊，要取權重最小的一條。 Dijstra算法描述。 集合S起始值為始發頂點N（作為新加入的頂點） 集合u起始值為除N以外的其他頂點。
1.遍歷新加入到S中節點的孩子節點（只在u不在s中）跟新它們到起始頂點N的距離（一開始為正無窮) 2.將u中到達N距離最短的頂點加入到s中 3.重復步驟1與2直到u為空。 注：s中頂點存儲的值為該頂點到達N的最小值 知識點介紹
truct cmp{ bool Operator()(int x,int y){ return result[x]>result[y]; }};PRiority_queue<int,vector<int>,cmp> que;自定義優先隊列<比較。 代碼實現
#include<iostream>#include<cstdio>#include<queue>#include<vector>using namespace std;#define INF 1<<29#define maxi 1002int map[maxi][maxi];int result[maxi];int s[maxi];vector<int>vec[maxi];struct cmp{ bool operator()(int x,int y){ return result[x]>result[y]; }};priority_queue<int,vector<int>,cmp> que;int dfs(int N){ int vis[maxi]={0}; vis[N]=1; while(!que.empty()){ int temp=que.top(); que.pop(); if(temp==1)return result[temp]; s[temp]=1; for(int i=1;i<N+1;i++) if(map[temp][i]!=INF&&s[i]==0){ if(map[temp][i]+result[temp]<result[i]) result[i]=map[temp][i]+result[temp]; if(vis[i]==0)que.push(i); vis[i]=1; } }}int main(){ int T,N; scanf("%d %d",&T,&N); for(int i=1;i<N+1;i++){ result[i]=INF; s[i]=0; for(int j=1;j<N+1;j++) map[i][j]=INF; } for(int i=1;i<T+1;i++){ int v1,v2,w; scanf("%d %d %d",&v1,&v2,&w); if(map[v1][v2]>w)map[v2][v1]=map[v1][v2]=w; } que.push(N); result[N]=0; printf("%d/n",dfs(N)); return 0;}新聞熱點
疑難解答
