塔子哥的环游之旅-腾讯2023笔试(codefun2000)
题目链接
塔子哥的环游之旅-腾讯2023笔试(codefun2000)
题目内容
塔子哥是一位热衷旅游的程序员。他所在的国家共有 n 个城市,编号从 1 到 n。这些城市之间有 m 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 1 的城市,他计划前往编号为 n 的城市进行旅游。
在这个国家,每个城市都有一个固定的时间 ai ,表示在该城市中转换交通工具所需的时间。特别地,在出发城市 1 和目的地城市 n,塔子哥不需要转换交通工具。
塔子哥可以自由选择乘坐飞机或火车前往下一个城市。他希望能够以最短的时间从出发城市抵达目的地城市。保证任意两个城市之间是连通的。
输入描述
输出描述
输出一个整数,表示塔子哥从出发城市到达目的地城市所需的最短时间。
样例1
输入
3 3
1 1 1
1 2 1 1
2 3 1 2
2 3 1 2
输出
3
样例1解释
塔子哥可以按照以下路线行进:从城市 1 乘坐飞机前往城市 2,耗时 1 个单位时间。在城市 2 中转换交通工具,耗时 1 个单位时间。从城市 2 乘坐火车前往城市 3,耗时 1 个单位时间。总共耗时 3 个单位时间,无法再缩短时间。
题解1
// 使用堆优化的迪杰斯特拉算法，时间复杂度是O((m+n)logn)，其中n是图中顶点个数，m是图中边的条数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int N = 1e5 + 10;int n, m, a[N];
LL dis[N][2]; // dis[i][0/1]表示到达编号为i的城市的飞机场/火车站所需的最少时间
bool vis[N][2]; // viss[i][0/1]表示途中是否经过编号为i的城市的飞机场/火车站，1：表示已经过，2：表示没有经过
struct node{int to, t, w; /*to表示边的终点t表示线路类别：0：该线路为飞机线路 1：该线路为火车线路w表示行驶该路线所需的时间 */
};
vector<node> edge[N];struct Vnode{int startNode;int t;LL w;/*to表示边的起点t表示线路类别：0：该线路为飞机线路 1：该线路为火车线路w表示行驶该路线所需的时间 */
}now;bool cmp(Vnode A, Vnode B){if(A.w != B.w) return A.w > B.w;return A.startNode > B.startNode;
}
// decltype为c++11中的关键字，decltype(&cmp)获取了比较函数cmp的类型
priority_queue<Vnode, vector<Vnode>, decltype(&cmp)> pq(cmp); // 小顶堆 void dijstra(){for(int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = INF;dis[1][1]= dis[1][0] = 0;pq.push({1,0,0}); // 从1号城市的飞机站出发， pq.push({1,1,0}); // 从1号城市的火车站出发， while(!pq.empty()){now = pq.top();pq.pop();int u = now.startNode;int ut = now.t;if(!vis[u][ut]){vis[u][ut] = 1;int sz = int(edge[u].size());for(int j = 0; j < sz; j++){int v = edge[u][j].to;int w = edge[u][j].w;int vt = edge[u][j].t;if(!vis[v][vt]){/*1)如果到达当前的站的类别与出发站的类别相同，则不需要转换交通工具所需的时间2)如果到达当前的站的类别与出发站的类别不相同，则需要转换交通工具所需的时间*/ if(vt == ut) dis[v][vt] = min(dis[v][vt], dis[u][vt] + w);else dis[v][vt] = min(dis[v][vt], dis[u][ut]+a[u]+w);pq.push({v,vt, dis[v][vt]});}}}}
}
int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1, u, v, w, t; i <= m; i++){scanf("%d%d%d%d", &u, &v, &w, &t);t--;edge[u].push_back({v, t, w});edge[v].push_back({u, t, w});}dijstra();printf("%lld\n", min(dis[n][0], dis[n][1]));return 0;
}