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.
当V很大时，用邻接矩阵表示图显然是不可取得 所以得用链式数据结构
定义一个结构体
struct node{ int to,cost; node *next; };原理就是让所有指向相同节点的元素加入到一个链表，让一个数组记录链表的末尾
加入数据：读取指向该节点链表末尾，再更新末尾指针 node * p=(node *)malloc(sizeof(node));p->next=pit[x]; //pit[] 为记录链表的末尾的数组pit[x]=p; //更新末尾指针读取数据：读取所有指向t的数据 for(node *p=pit[t];p;p=p->next)当然这个题用邻接矩阵完全也没问题，只是以该模板题为例而已
#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #define MAX_N 1010 using namespace std; int V,E; struct node{ int to,cost; node *next; }; node *pit[MAX_N]; void add_data(int x,int y,int v){ node *p=(node *)malloc(sizeof(node)); p->to=y; p->cost=v; p->next=pit[x]; pit[x]=p; } int d[MAX_N]; int Dijkstra(){ memset(d,0x3f,sizeof(d)); d[1]=0; priority_queue<pair<int,int> > que; que.push(make_pair(0,1)); while(!que.empty()){ int t=que.top().second,v=que.top().first;que.pop(); if(v>d[t]) continue; for(node *p=pit[t];p;p=p->next){ if(d[t]+p->cost<d[p->to]){ d[p->to]=d[t]+p->cost; que.push(make_pair(d[p->to],p->to)); } } } return d[V]; } void del(){ for(int i=1;i<=V;i++) for(node *p=pit[i],*t;p;p=t){ t=p->next; free(p); } } int main() { scanf("%d%d",&E,&V); int x,y,v; for(int i=0;i<E;i++){ scanf("%d%d%d",&x,&y,&v); add_data(x,y,v); add_data(y,x,v); } printf("%d\n",Dijkstra()); del(); return 0; }