[C++知识库]2.13总结

1.上午两个半小时

完成了两个题目。

P2910 [USACO08OPEN]Clear And Present Danger S

P2910 [USACO08OPEN]Clear And Present Danger S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)s

思路

直接用弗洛伊德算法的模板就可以了，思路相似。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,sum=0;
    int a[10001],b[101][101];
    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",&b[i][j]);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                b[j][k]=min(b[j][i]+b[i][k],b[j][k]);
    for(int i=2; i<=m; i++)
        sum=sum+b[a[i-1]][a[i]];
    //sum=sum+b[0][a[0]];
    //sum=sum+b[a[m-1]][n-1];
    printf("%d",sum);
    return 0;
}

P1395 租用游艇

P1359 租用游艇 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

还是和弗洛伊德算法的思路相似，套用模板就可以了。

代码实现

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[201][201],b[201]= {0};
    for(int i=1; i<n; i++)//站与站之间的租金
        for(int j=i+1; j<=n; j++)
            scanf("%d",&a[i][j]);
    //for(int i=1; i<=n; i++)
        //b[i]=9999999;
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<=i; j++)
        {
            if(b[i]==0)//如果还是最初的就更新
                b[i]=b[j]+a[j][i];
            else
            {
            if(b[i]>b[j]+a[j][i])//一直找小的
                b[i]=b[j]+a[j][i];
            else
                b[i]=b[i];
            }
        }
    }
    printf("%d",b[n]);
    return 0;
}

2.下午四个半小时

听学长讲课，然后完成了一个题目。

P3371 【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

套用迪杰斯特拉算法的模板。

代码实现

#include<bits/stdc++.h>
using namespace std;
int head[10001];
int n,m,s,o,p,q,cnt;
bool vis[10001];
long long dist[10001];
struct Edge
{
    int to;
    int weight;
    int next;
}edge[500001];
void addedge(int a,int b,int v)
{
    cnt++;
    edge[cnt].to=b;
    edge[cnt].weight=v;
    edge[cnt].next=head[a];
    head[a]=cnt;
}
void dij()
{
    for(int i=1;i<=n;i++)
    {
        dist[i]=2147483647;
        vis[i]=false;
    }
    dist[s]=0;
    int idex=s;
    while(!vis[idex])
    {
        vis[idex]=true;
        for(int i=head[idex];i!=0;i=edge[i].next)
        {
            if(!vis[edge[i].to]&&dist[edge[i].to]>dist[idex]+edge[i].weight)
            {
                dist[edge[i].to]=dist[idex]+edge[i].weight;
            }
        }
        int Min=2147483647;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&Min>dist[i])
            {
                Min=dist[i];
                idex=i;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",dist[i]);
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&o,&p,&q);
        addedge(o,p,q);
    }
    dij();
    return 0;
}

3.晚上两个小时

P4779【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

和弱化版的区别就是点的个数增加了很多，如果还用刚刚一样的代码，肯定会超时，所以我们要用到一个新的算法-----优先队列。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
const int zz=0x7fffffff;
const int M=500001;
int n,m,s=1,cnt,e,a,b,c;
int head[N],dist[N];
bool vis[N];
struct edge
{
    int to;
    int weight;
    int next;
} edge[M];
struct node
{
    int idex;
    int v;
    bool operator<(const node &x) const
    {
        return x.v<v;
    }
};
void addedge(int a,int b,int v)
{
    cnt++;
    edge[cnt].to=b;
    edge[cnt].weight=v;
    edge[cnt].next=head[a];
    head[a]=cnt;
}
void dij()
{
    for(int i=1; i<=n; i++)
    {
        vis[i]=false;
        dist[i]=zz;
    }
    dist[s]=0;
    priority_queue<node> q;
    q.push({s,0});
    while(q.size())
    {
        int idex=q.top().idex;
        q.pop();
        if(vis[idex])
            continue;
        vis[idex]=true;
        for(int i=head[idex]; i; i=edge[i].next)
        {
            if(dist[edge[i].to]>dist[idex]+edge[i].weight)
                dist[edge[i].to]=dist[idex]+edge[i].weight;
            if(!vis[edge[i].to])
                q.push({edge[i].to,dist[edge[i].to]});
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dist[i]);
}
int main()
{
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        addedge(a,b,c);
    }
    dij();
    return 0;
}