品牌运营,泉州优化怎么做seo,网站备案背景幕布是什么,wordpress线下安装教程题目链接 塔子哥的环游之旅-腾讯2023笔试(codefun2000)
题目内容 塔子哥是一位热衷旅游的程序员。他所在的国家共有 n 个城市,编号从 1 到 n。这些城市之间有 m 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 1 的城市,他计划前往编号为 n 的城市进行旅游…题目链接 塔子哥的环游之旅-腾讯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((mn)logn)其中n是图中顶点个数m是图中边的条数
#includebits/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表示行驶该路线所需的时间 */
};
vectornode 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为c11中的关键字decltype(cmp)获取了比较函数cmp的类型
priority_queueVnode, vectorVnode, 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;
}
