[Acwing] 最优乘车 最短路建图

前言

考虑建图 用 s s t r e a m sstream sstream 处理读入一行很巧妙 传送门 :

思路

我们可以 给 一条路线上的所有点都连一条边

这样子处理的话,我们就可以不用考虑 中途是否换车的问题

我们只需要都连一条边 并且 付边权为 1 1 1 即可

最后跑一遍最短路就行

CODE

#include 
#include 
#include 
#include 
using namespace std;
const int N = 550;
int g[N][N];
int stop[N];
int dist[N];
bool st[N];
int n,m;

int dij()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0 ;

    for(int i = 0;im>>n;
    memset(g,0x3f,sizeof g);
    string line;
    getline(cin,line);///处理最后的回车

    while(m -- )
    {
        string line;
        getline(cin,line);

        stringstream ssin(line);///过滤数据中的空格

        int cnt = 0 , p ;

        while(ssin>>p)
        stop[cnt++] = p;
        ///将所有的停车点 相互结合来建图

        
        for(int i=0;i