国庆day1总结--上午

Crash_Man_CHN · 2025-10-04 21:23:31 · 个人记录

最短路问题总结（暂无SPFA）

Floyd算法

思想：dp，通过中间顶点优化任意两点对最短路径

原理：i到j的最短路径 = min(直接路径, i→k→j路径),得出转移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

步骤：

初始化距离矩阵（i,i都是0,其余无穷大） (初始化)
枚举中间点k，更新所有i,j的距离 (转移)

最终矩阵存所有点对最短路径 (答案)

时间复杂度: O(n^3)

实现代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2005;
int n,m,dis[maxn][maxn],e[maxn][maxn];
void floyd()
{
for(int k=1;k<=n;k++)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
        }
    }
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
memset(e,0x3f,sizeof e);
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)e[i][i]=0;
for(int i=1;i<=m;i++)
{
    int u,v,w;
    cin>>u>>v>>w;
    e[u][v]=min(e[u][v],w);
    e[v][u]=min(e[v][u],w);
}
floyd();
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        cout<<e[i][j]<<" ";
    }
    cout<<"\n";
}
return 0;
}

例题

1.B3647 【模板】Floyd

直接把模板打上去

2.P2888 [USACO07NOV] Cow Hurdles S

首先考虑重边用min(dp[s][e],h)，其次题目求得答案是计算出路径上最高的栏的高度的最小值.所以状态转移方程变为dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int dis[N][N],n,m,t; 
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],max(dis[i][k],dis[k][j]));
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>t;
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=n;i++)dis[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int s,e,h;
        cin>>s>>e>>h;
        dis[s][e]=min(dis[s][e],h);
    }
    floyd();
    for(int i=1;i<=t;i++)
    {
        int a,b;
        cin>>a>>b;
        if(dis[a][b]<0x3f3f3f3f)cout<<dis[a][b]<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}

Dijkstra算法

思想：贪心，求单源到所有顶点最短路径（边权非负）

原理：每次选最近未确定顶点，以此更新其他顶点距离

步骤：

初始化源点距离为0，其余为无穷大
选距离最小的未确定顶点，标记并更新邻点距离

重复n次，得源点到所有顶点最短路径

时间复杂度: O(m*log(n))

实现代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,s;
int dis[N];
bool vis[N];
struct node
{
int id,w;
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;
pq.push({s,dis[s]});
while(!pq.empty())
{
    node t=pq.top();
    pq.pop();
    int x=t.id;
    if(vis[x]==1)continue;
    vis[x]=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]+w<dis[y])
        {
            dis[y]=dis[x]+w;
            pq.push({y,dis[y]});
        }
    }
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
    int u,v,w;
    cin>>u>>v>>w;
    e[u].push_back({v,w});
}
dijkstra(s);
for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
return 0;
}

例题

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

模板题

2.P4568 [JLOI2011] 飞行路线

首先用优先队列，然后用重载运算符，但是这道题目有两种情况 1.没用优惠 2.用了优惠，所以我们要写两个判断，最后所有起点一律从1开始即可

code

v#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,k,s,t;
int dis[N][15];
bool vis[N][15];
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]+0<dis[y][l+1])
            {
                dis[y][l+1]=dis[x][l]+0;
                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>>s>>t;
    s++,t++;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        u++,v++;
        e[u].push_back({v,w});
        e[v].push_back({u,w});      
    }
    dijkstra(s);
    int ans=1e18;
    for(int i=0;i<=k;i++)ans=min(ans,dis[t][i]);
    cout<<ans;
    return 0;
}