链式前项星板子题目

最短路

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int maxx =1e6+5;
const int N= 10000;
const int INF= 0x3f3f3f3f;
int n,m,v,u,w;
struct node {int to;  // 这条边的终点 int next;  //下一条边的终点 int len;   //权值 
}edge[maxx];
int head[maxx];
int cot=0;
void addeage(int u,int v,int w){   //起点  终点 权值 edge[cot].to=v;   //edge[cot].next=head[u];  // edge[cot].len=w; // head[u]=cot++;}
int a[N],b[N]; //a 路程   b 标记 
void diji(int s)
{for (int i=1;i<=n;i++)  a[i]=INF,b[i]=0; a[s]=0;while(1){int k=-1,len=INF;  //*for(int i=1;i<=n;i++){   if(!b[i]&&len>a[i]){   //len 用于确定当前最短 k=i;len=a[i];}}if(k==-1)   break;b[k]=1;for(int i=head[k];i!=-1;i=edge[i].next){int t=edge[i].to;if(!b[t]&&a[t]>a[k]+edge[i].len)a[t]=a[k]+edge[i].len;}}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){if(!n&&!m)break;memset(head,-1,sizeof(head));while(m--){scanf("%d%d%d",&u,&v,&w);addeage(u,v,w);addeage(v,u,w);}diji(1);printf("%d\n",a[n]);}return 0;
}

b题

一个人的旅行

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx =1e6+5;
const int N= 10000;
const int INF= 0x3f3f3f3f;
int n,m,v,u,w,l,T;
int dp,start[2000],sens[2000]; 
struct node {int to;  // 这条边的终点 int next;  //下一条边的终点 int len;   //权值 
}edge[maxx];
int head[maxx];
int cot=0;
void addeage(int u,int v,int w){   //起点  终点 权值 edge[cot].to=v;   //edge[cot].next=head[u];  // edge[cot].len=w; // head[u]=cot++;}
int a[N],b[N]; //a 路程   b 标记 
void diji(int s)
{for (int i=1;i<=l;i++)  a[i]=INF,b[i]=0; a[s]=0;while(1){int k=-1,len=INF;  //*for(int i=1;i<=l;i++){   if(!b[i]&&len>a[i]){   //len 用于确定当前最短 k=i;len=a[i];}}if(k==-1)   break;b[k]=1;for(int i=head[k];i!=-1;i=edge[i].next){int t=edge[i].to;if(!b[t]&&a[t]>a[k]+edge[i].len)a[t]=a[k]+edge[i].len;}}
}
int main()
{while(scanf("%d%d%d",&T,&n,&m)!=EOF){if(!n&&!m)break;memset(head,-1,sizeof(head));cot=0;dp=INF;l=-INF;while(T--){scanf("%d%d%d",&u,&v,&w);addeage(u,v,w);addeage(v,u,w);l=max(max(u,v),l);}for(int i=0;i<n;i++)scanf("%d",&start[i]);for(int i=0;i<m;i++)scanf("%d",&sens[i]);for(int i=0;i<n;i++){diji(start[i]);for(int j=0;j<m;j++){dp=min(a[sens[j]],dp);}}printf("%d\n",dp);}return 0;
}

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。

Output

输出草儿能去某个喜欢的城市的最短时间。

Sample Input

6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Sample Output

9

链式前项星

是用数组代替 指针 避免了因为出现多次molloc 出现超时和多次使用指针而导致结果可能混乱

一般 输入的信息都是3个  a点和b点 和他们之间的权值

struct node {int to;  // 这条边的终点 int next;  //下一条边的终点 int len;   //权值 
}edge[maxx];

一般使用链式前项星都是无方向

所以 在进行建路 时 a和 b b和 a 都应该输入

下面是输入图即建立的过程

int head[maxx];
int cot=0;
void addeage(int u,int v,int w){   //起点  终点 权值 edge[cot].to=v;   //edge[cot].next=head[u];  // edge[cot].len=w; // head[u]=cot++;}

要注意当前所指的起点和终点都是无方向的所以再进行输入时应该

	while(m--){scanf("%d%d%d",&u,&v,&w);addeage(u,v,w);addeage(v,u,w);}

下面是做题使用的 dijikstra 算法

void diji(int s)
{for (int i=1;i<=n;i++)  a[i]=INF,b[i]=0; a[s]=0;while(1){int k=-1,len=INF;  //*for(int i=1;i<=n;i++){   if(!b[i]&&len>a[i]){   //len 用于确定当前最短 k=i;len=a[i];}}if(k==-1)   break;b[k]=1;for(int i=head[k];i!=-1;i=edge[i].next){int t=edge[i].to;if(!b[t]&&a[t]>a[k]+edge[i].len)a[t]=a[k]+edge[i].len;}}
}

a[] 数组是用来记录最短路的所以应该先定义为 inf 即可以认为为无限大

b[]数组是用记录该点是否已被 out掉  注意是out 而不是访问过  当我们在 一个点的时候 

如

当前我们在1点 可以去2，3，6三点 为了确定 离a点最近的我们要依次访问这3点 但最后发现 2点最近所以 2点out 

即我们走到了 2点 同时将它标记为1 即下次 无论到那个点时不会回来再次访问2点 要不因为我们当时记录是无限 有可能莫名成

环导致出错；

最后

这里

	for(int i=head[k];i!=-1;i=edge[i].next){int t=edge[i].to;if(!b[t]&&a[t]>a[k]+edge[i].len)a[t]=a[k]+edge[i].len;}}

我们在什么已经设置了 edge[i].next 为head[u];

head[]我们初始化为-1 所以又把edge【i】.next值赋给 i;所以当 hend[u]为尾节点 即后面没有则为-1 则跳出

为了防止多组输入应该在主函数或者定义一个 初始化函数

把head【】初始化为-1；cot初始化为0