SCAU2020春季个人排位赛div2 #1A

SCAU2020春季个人排位赛div2 #1A

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

2.题目大意
给你N个路口，要从路口A到另外一个路口C要花费C时间，问你从1->n所需最短时间。

3.解题思路
建图，用floyd求最短路是最容易想到的了。
因为这题是单源最短路，即计算一个节点到其他所有节点的最短路径。
用Dijkstra似乎效率更好，所以补充Dijkstra的做法。
还有Dijkstra+队列

4.floyd
思想是：从i到j，无非就是直接i->j，或者借中间路先i->k,然后k->j.
可以有这样的式子：

 if(a[j][i] + a[i][k] < a[j][k]){a[j][k] = a[j][i] + a[i][k];}

5.Dijkstra

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过中间点k）比原来距离（不经过中间点k）短，则修改顶点u的距离值，修改后的距离值为中间点k的距离加上边上的权。d.重复步骤b和c直到所有顶点都包含在S中。

如果用队列当数据大时能效率更高
//
上面是Dijkstra+队列的一道题。
AC代码

//floyd
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
const int maxn = 120;
const int INF =0x3f3f3f3f;
using namespace std;
#define LL long long
LL graph[maxn][maxn];
LL cost[maxn][maxn];
int n,m;
int x,y,c,t;
void floyd()
{for(int k = 0; k <=n; k++)//中间点{for(int i= 0; i<=n ; i++)//起点{for(int j = 0; j<=n; j++)//终点{// 直接i->j，或者借中间路先i->k,然后k-&aph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);}}}
}
int main()
{while(scanf("%d%d",&n,&m) !=EOF && !(!n && !m)){for(int i = 0; i<=n; i++){for(int j = 0; j<=n; j++){graph[i][j] = graph[j][i] = INF;}}for(int i = 0; i<=n; i++)graph[i][i] = 0;for(int  i = 0; i<m; i++){cin>>x>>y>>c;graph[x][y] = graph[y][x] = c;}floyd();printf("%lldn",graph[1][n]);}return 0;
}

//Dijkstra
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
const int maxn = 120;
const int INF =0x3f3f3f3f;
using namespace std;
#define LL long long
LL graph[maxn][maxn];
LL dis[maxn],visit[maxn];
int n,m;
int x,y,c,t;
void Dijkstra(int n)
{int minid , minn;for(int i = 1; i<=n; i++) //从A作为源点{dis[i] = graph[1][i]; //把A到其他点的距离赋值visit[i] = 0;//标记，0就是还没有连，1就是已经连}visit[1] = 1; //从A开始作为源点for(int i = 1; i<=n; i++){minn = INF;for(int  j= 1; j<=n; j++){if(!visit[j] && dis[j] < minn) // 找到当前点到其他还没有被标记的点的最短路径。{minn = dis[j]; minid = j;//找到当前点到某个点的距离是最小的，那么这两个点连起来。}}visit[minid] = 1; //标记for(int j = 1; j<=n; j++) // 这个时候更新当前点，更新为minid为新的当前点，那么当前点到其他点的距离就需要更新了。{if(!visit[j] && dis[minid] + graph[minid][j] < dis[j]) //  { //如果经过minid到达当前点的距离比不经过minid(直接到达当前点)的距离短，那就选择先经过minid再到当前点。dis[j] = graph[minid][j] + dis[minid];}}}
}int main()
{while(scanf("%d%d",&n,&m) !=EOF && !(!n && !m)){for(int i = 0; i<=n; i++){for(int j = 0; j<=n; j++){graph[i][j] = graph[j][i] = INF;}}for(int  i = 0; i<m; i++){cin>>x>>y>>c;graph[x][y] = graph[y][x] = c;}Dijkstra(n);printf("%lldn",dis[n]);}return 0;
}

//Dijkstra+队列
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
const int maxn = 1200;
const int INF =0x3f3f3f3f;
using namespace std;
#define LL long long
int dis[maxn], pre[maxn];
int n,m;
int x,y,cost,s,t;
struct node{int num;int dis;bool friend operator <(node a, node b){return a.dis > b.dis;}
};
vector<node>a[maxn];
bool visit[maxn];
void dijkstra()
{memset(visit,false,sizeof(visit));priority_queue<node>q;for(int i = 0; i<=n; i++)dis[i] = INF;dis[1] = 0;node no;no.num = 1;no.dis = 0;q.push(no);while(!q.empty()){node u = q.top();q.pop();int x = u.num;if(visit[x]) continue;visit[x] =true;int len = a[x].size();for(int i = 0; i<len; i++){node t = a[x][i];if(dis[t.num] > t.dis + u.dis){dis[t.num] = t.dis + u.dis;t.dis =dis[t.num];q.push(t);}}}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF && !(!n && !m)){for(int i = 0; i<n; i++)a[i].clear();for(int i = 0; i <m; i++){cin>>x>>y>>cost;a[x].push_back((node){y,cost});a[y].push_back((node){x,cost});}dijkstra();printf("%dn",dis[n]);}return 0;
}