- [P1359 租用游艇](https://www.luogu.com.cn/problem/P1359)
题解：这题就是求1到n的最短路，可以看到n<=200，所以这题可以用floyd来解，注意的是它的输入是半矩阵的，要正确存图。
#include#define inf 0x3f3f3f3fint e[201][201];int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j)e[i][j]=0; else e[i][j]=inf; } } for(int i=1;i<=n-1;i++) { for(int j=i+1;j<=n;j++) { scanf("%d",&e[i][j]); } } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j]; printf("%d",e[1][n]); return 0;}
- [P2910 [USACO08OPEN]Clear And Present Danger S]
(https://www.luogu.com.cn/problem/P2910)
题解：这题观察数据，N<=100,且是多元路径最短问题，也可以用floyd快速解题，先求出任意两个点之间的最短路径，然后把必经之路上的最短距离加起来即可。
#includeint e[101][101],a[10001];int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&e[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) if(e[j][k]>e[j][i]+e[i][k]) e[j][k]=e[j][i]+e[i][k]; int ans=0; for(int i=2;i<=m;i++) ans+=e[a[i-1]][a[i]]; printf("%d",ans); return 0;}
- [P1339 [USACO09OCT]Heat Wave G](https://www.luogu.com.cn/problem/P1339)
题解：个人认为这就是迪杰斯特拉算法的模板题，就是如果用邻接矩阵存图的话可能有个坑，第一它是无向图，第二如果输入的边的边权比已有的小的话才能覆盖，否则会错误。
#include#define inf 0x3f3f3f3fint e[2501][2501],book[2501],dis[2501];int main(){ int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j)e[i][j]=0; else e[i][j]=inf; } } for(int i=1;i<=m;i++) { int t1,t2,t3; scanf("%d%d%d",&t1,&t2,&t3); if(t3dis[u]+e[u][j]) dis[j]=dis[u]+e[u][j]; } } } printf("%d",dis[t]); return 0;}
- [P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)
题解：这题明显用迪杰斯特拉算法，但用邻接矩阵存图会爆内存，最多拿70分，所以这里我们采用链式前向星。我们先定义一个结构体，把所有边用个结构体数组存起来，to代表到达的顶点，v代表边权，next代表同起点的上一条边在数组里的下标。head数组记录以i点出发的边在数组中的下标，一旦被覆盖，就用新边的next记录被覆盖边的位置。
代码实现如下：
#include#include#define inf 2147483647struct Node{ int to; int v; int next;} edge[500001];int book[10001],dis[10001],head[10001],cnt;int n,m,s;// 链式前向星void add(int a,int b,int c){ cnt++;//下标 edge[cnt].to=b; edge[cnt].v=c; edge[cnt].next=head[a]; head[a]=cnt;}void dij(){ int idx=s;//把起点看做扩展点 while(1) { book[idx]=1; for(int i=head[idx]; i!=-1; i=edge[i].next) { int a=idx,b=edge[i].to,v=edge[i].v; if(dis[b]>dis[a]+v)//我这里没标记!!!! dis[b]=dis[a]+v; } int min=inf; for(int i=1; i<=n; i++) { if(book[i]==0&&min>dis[i]) { min=dis[i]; idx=i; } } if(book[idx])break;//所有点的最短路径都求出来了 }}int main(){ scanf("%d%d%d",&n,&m,&s); for(int i=1; i<=n; i++) { head[i]=-1; dis[i]=inf; } dis[s]=0; for(int i=1; i<=m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } dij(); for(int i=1; i<=n; i++) printf("%d ",dis[i]); return 0;}