2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛)(F题)(最短路)_gplt天梯赛真题

 

G 国有 n 个城市，城市之间由 m 条双向直达铁路连接，一条铁路连接了两个不同的城市，并且乘坐第 iii 条铁路需要wi 个单位时间。如果两个城市之间没有直达的铁路，那么则必须要通过其他城市换乘才能相互可达。换乘不需要花费时间，但是 lbromine 非常不喜欢换乘。现在 lbromine 想要从 1 号城市到达 n 号城市，他想知道他最少需要经过多少个城市(包括城市 1和城市 n )，以及在保证经过城市最少的情况下需要花费的最少时间。

输入描述:

第一行两个正整数 n，m 表示 G国有 n 个城市和 m 条铁路。

接下来 m 行，每行三个整数 ui,vi,wi​ 表示 lbromine 可以花费 wi​ 的时间在 ui 和 vi​ 之间旅行。

数据保证 1 号城市和 n 号城市联通。

输出描述:

输出一行两个整数，第一个整数表示lbromine最少需要经过多少个城市，第二个整数表示保证经过城市最少的情况下需要花费的最少时间，两个整数之间用空格隔开。

示例1

输入

4 4
1 2 1
2 3 1
3 4 1
1 4 5

输出

2 5

备注:

对于 100% 的数据 1≤n≤100000 , n−1≤m≤200000, 1≤wi​≤10000

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;
int n,m;
vector<pair<int,int>>adj[MAXN];
bool visited[MAXN];
int dist[MAXN];
int cityNum[MAXN];
struct Node{
    int id;
    int cityNum;
    int dist;
    bool operator < (const Node& other) const
    {
        if (cityNum != other.cityNum)
        {
            return cityNum > other.cityNum;
        }
        else
            return dist > other.dist;
    }
};
void dijkstra(){
    memset(visited , 0 , sizeof(visited));
    memset(dist , INF , sizeof(dist));
    memset(cityNum , INF , sizeof(cityNum));
    priority_queue<Node>pq;
    pq.push({1,1,0});
    dist[1] = 0;
    cityNum[1] = 1;
    while(!pq.empty()){
        int u=pq.top().id;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for(auto t:adj[u]){
            int v=t.first,w=t.second;
            if (cityNum[v] >= cityNum[u] + 1)
            {
                if (dist[v] > dist[u] + w)
                {
                    dist[v] = dist[u] + w;
                    cityNum[v] = cityNum[u] + 1;
                    pq.push({ v,  cityNum[v],dist[v]});
                }
            }
        }
    }
    cout << cityNum[n] << " " << dist[n] << endl;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra();
}