上學(xué)要遲到了

題目

牛牛早上起床一看，自己睡過了，趕緊起床準(zhǔn)備去學(xué)校，他去學(xué)校只有兩種方式，坐公交車和步行，牛牛去學(xué)校是一條直線，這條直線上總共有 $n$ 個車站，車站之間的距離都是相等的，每個車站只有一種公交車$a_i$，每個公交車只在對應(yīng)的公交站停車，每個公交車的速度也不一樣，第 $i$ 種公交車過一站的時間需要 $t_i$，并且公交車是單向行駛，只能從左到到右，走路可以任意走，然而牛牛自己步行走一站需要的時間為 $T$，恰好牛牛家和學(xué)校都在某一個站點，分別為 $s$ 和 $t$，問最少需要多少時間牛牛才能到學(xué)校？

分析

直接建圖跑最短路，注意公交車是單向的，而人可以雙向行走

代碼

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<random> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; mt19937 rnd(233); typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const int N=100010; int h[N],e[N],ne[N],w[N],idx; int n,m,s,t,T; int cost[N]; int last[N]; bool st[N]; int dist[N]; void add(int a,int b,int c) {e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++; } int dijkstra(int start,int ed) {memset(dist,0x3f,sizeof dist);dist[start]=0;priority_queue<pii,vector<pii>,greater<pii> >q;q.push({0,start});while(q.size()){int t=q.top().second;q.pop();if(st[t]) continue;st[t]=1;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]) {dist[j]=dist[t]+w[i];q.push({dist[j],j});}}if(t+1<=n) {if(dist[t+1]>dist[t]+T){dist[t+1]=dist[t]+T;q.push({dist[t+1],t+1});}}if(t-1>0){if(dist[t-1]>dist[t]+T){dist[t-1]=dist[t]+T;q.push({dist[t-1],t-1});}}}return dist[ed]; }int main() {IO;memset(h,-1,sizeof h);cin>>n>>m>>s>>t>>T;for(int i=1;i<=m;i++) cin>>cost[i];for(int i=1;i<=n;i++){int a;cin>>a;if(last[a]) add(last[a],i,cost[a]);last[a]=i;}cout<<dijkstra(s,t)<<'\n';return 0; }

總結(jié)

以上是生活随笔為你收集整理的上学要迟到了【最短路转化】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。