国庆day1最短路考试--下午

· · 个人记录

前言

都有思路但是没写对，（要是写对210往上）

T1

考场思路

Dijkstra

正确思路

首先理解一点点x(u1,u2)走到点y(v1,v2)的权值是abs(v1-v2),其次我们就可以开始跑最短路，核心思路：枚举每个点若连的点相同就可以取最小值所以可以用优化后的SPFA

T2

输入写错了把m写成了n,思路是上午原题

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int n,m,k,s,t;
int dis[N][N];
bool vis[N][N];
struct node
{
    int id,w,cnt;
    bool operator < (const node & tmp) const
    {
        return w>tmp.w;
    }
};
vector<node> e[N];
priority_queue<node> pq;
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof(vis));
    dis[s][0]=0;
    pq.push({s,dis[s][0],0});
    while(!pq.empty())
    {
        node t=pq.top();
        pq.pop();
        int x=t.id,l=t.cnt;
        if(vis[x][l]==1)continue;
        vis[x][l]=1;
        for(int i=0;i<e[x].size();i++)
        {
            int y=e[x][i].id;
            int w=e[x][i].w;
            if(dis[x][l]+w<dis[y][l])
            {
                dis[y][l]=dis[x][l]+w;
                pq.push({y,dis[y][l],l});
            }
            if(l<k&&dis[x][l]+w/2<dis[y][l+1])
            {
                dis[y][l+1]=dis[x][l]+w/2;
                pq.push({y,dis[y][l+1],l+1});
            }
        }
    }
    return ;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});      
    }
    dijkstra(1);
    int ans=1e18;
    for(int i=0;i<=k;i++)ans=min(ans,dis[n][i]);
    cout<<ans;
    return 0;
}

T3

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int dis[N][N],n,m;
void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}
void check()
{
    int sum=0x3f3f3f3f3f3f3f3f;
    for(int u=1;u<n;u++)
    {
        for(int w=u+1;w<=n;w++)
        {
            int ans=0;
            for(int i=1;i<n;i++)
            {
                for(int j=i+1;j<=n;j++)
                {
                    ans+=min(min(dis[i][u]+dis[w][j],dis[i][w]+dis[u][j]),dis[i][j]);
                }
            }
            sum=min(sum,ans);
        }
    }
    cout<<sum;
    return ;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=n;i++)dis[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        dis[x][y]=w;
        dis[y][x]=w;
    }
    floyd();
    check();
    return 0;
}