【Acwing】【单源最短路建图】920. 最优乘车

太过爱你忘了你带给我的痛 2024-04-01 16:52 76阅读 0赞

[920. 最优乘车 - AcWing题库][920. _ - AcWing]

题意：

![7c30b54756844cdfad358c70575c4430.png][]

**思路：**

**图论题的重点在于建模和建图，其余的打板子即可**

**在建图的过程中需要注意：**

**1.结点的含义是什么**

**2.边权的含义是什么，一般边权定义为题目需要维护的东西，也有可能就是答案**

比如这道题，结点就是各个车站，题目要求换乘次数，换乘次数为坐车次数-1，因此我们用边权维护坐车次数

因此，对于同一路线的车，我们建一条边权为1的边，表示只坐过一次车

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e2+10,mxe=5e2+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    queue<int> q;
    string s;
    int m,n,len=0,p,tot=0;
    int a[mxn],head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;len=0;
        s.clear();
        for(int i=0;i<=n;i++){
            head[i]=-1;
            dis[i]=mnf;
        }
        while(!q.empty()) q.pop();
    }
    void spfa(){
        dis[1]=0;
        vis[1]=1;
        q.push(1);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u]+edge[i].w){
                    dis[edge[i].to]=dis[u]+edge[i].w;
                    if(!vis[edge[i].to]){
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>m>>n;
        init();
        getline(cin,s);
        for(int i=1;i<=m;i++){
            len=0;
            getline(cin,s);
            stringstream ssin(s);
            while(ssin>>p) a[++len]=p; 
            for(int i=1;i<=len;i++){
                for(int j=i+1;j<=len;j++){
                    //cout<<a[i]<<" "<<a[j]<<'\n';
                    add(a[i],a[j],1);
                }
            }
        }
        spfa();
        if(dis[n]==mnf) cout<<"NO"<<'\n';
        else cout<<dis[n]-1<<'\n';
    }

[920. _ - AcWing]: https://www.acwing.com/problem/content/922/
[7c30b54756844cdfad358c70575c4430.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/915b98531c794236b76a1562a0e7f212.png