題目鏈接
塔子哥的環(huán)游之旅-騰訊2023筆試(codefun2000)

題目內容

塔子哥是一位熱衷旅游的程序員。他所在的國家共有 n 個城市,編號從 1 到 n。這些城市之間有 m 條雙向的交通線路,分別為飛機線路和火車線路。塔子哥起始位于編號為 1 的城市,他計劃前往編號為 n 的城市進行旅游。
在這個國家,每個城市都有一個固定的時間 ai ,表示在該城市中轉換交通工具所需的時間。特別地,在出發(fā)城市 1 和目的地城市 n,塔子哥不需要轉換交通工具。
塔子哥可以自由選擇乘坐飛機或火車前往下一個城市。他希望能夠以最短的時間從出發(fā)城市抵達目的地城市。保證任意兩個城市之間是連通的。

輸入描述

輸出描述

輸出一個整數,表示塔子哥從出發(fā)城市到達目的地城市所需的最短時間。

樣例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 個單位時間?？偣埠臅r 3 個單位時間,無法再縮短時間。

題解1

// 使用堆優(yōu)化的迪杰斯特拉算法，時間復雜度是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號城市的飛機站出發(fā)， pq.push({1,1,0}); // 從1號城市的火車站出發(fā)， 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)如果到達當前的站的類別與出發(fā)站的類別相同，則不需要轉換交通工具所需的時間2)如果到達當前的站的類別與出發(fā)站的類別不相同，則需要轉換交通工具所需的時間*/ 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;
}