租用游艇，Clear And Present Danger S，Heat Wave G，单源最短路径（弱化版）

- [P1359 租用游艇](https://www.luogu.com.cn/problem/P1359)

题解：这题就是求1到n的最短路，可以看到n<=200，所以这题可以用floyd来解，注意的是它的输入是半矩阵的，要正确存图。

#include
#define inf 0x3f3f3f3f
int 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快速解题，先求出任意两个点之间的最短路径，然后把必经之路上的最短距离加起来即可。

#include
int 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 0x3f3f3f3f
int 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 2147483647
struct 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;
}