P5767 [NOI1997]最优乘车

这不是暑假做的建模题吗。。。

\(g[i][j]\)为不考虑换乘情况下\(i->j\)的最短距离（依题意显然为0）

再跑\(dijkstra\)判断换乘情况下\(1\)号点到\(n\)号点的最短距离

const int N=510;
int g[N][N];
int dist[N];
bool vis[N];
int sta[N];
int n,m;

void dijkstra()
{
    for(int i=1;i<=n;i++) dist[i]=g[1][i];

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j] && (t==-1 || dist[t] > dist[j]))
                t=j;
        vis[t]=true;

        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]+1);
    }
}

int main()
{
    scanf("%d%d\n",&m,&n);

    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++) g[i][i]=0;

    while(m--)
    {
        string line;
        getline(cin,line);
        stringstream ss(line);
        int x,cnt=0;
        while(ss>>x) sta[cnt++]=x;

        for(int i=0;i<cnt;i++)
            for(int j=i+1;j<cnt;j++)
            {
                int x=sta[i],y=sta[j];
                g[x][y]=0;
            }
    }

    dijkstra();

    if(dist[n] == INF) puts("NO");
    else cout<<dist[n]<<endl;

    //system("pause");
}

其他解：
将一条线路上的点之间的距离全设为\(1\)，在此情况下求\(1->n\)的最短距离，最短距离减一即为换乘次数，边权全为\(1\)，用\(bfs\)求最短路。

const int N=510;
int g[N][N];
int dist[N];
int sta[N];
int n,m;

int bfs()
{
    memset(dist,-1,sizeof dist);
    queue<int> q;
    dist[1]=0;
    q.push(1);

    while(q.size())
    {
        int t=q.front();
        q.pop();

        if(t == n) return dist[t];

        for(int i=1;i<=n;i++)
            if(g[t][i] && dist[i] == -1)
            {
                dist[i]=dist[t]+1;
                q.push(i);
            }
    }
    return -1;
}

int main()
{
    scanf("%d%d\n",&m,&n);

    while(m--)
    {
        string line;
        getline(cin,line);
        stringstream ss(line);
        int x,cnt=0;
        while(ss>>x) sta[cnt++]=x;

        for(int i=0;i<cnt;i++)
            for(int j=i+1;j<cnt;j++)
            {
                int x=sta[i],y=sta[j];
                g[x][y]=1;
            }
    }

    int t=bfs();

    if(t == -1) puts("NO");
    else cout<<max(t-1,0)<<endl;

    //system("pause");
}