全国的网站建设,快速开发工具网站,wordpress上传图片路径修改,遵义市住房城乡建设局网站上学要迟到了
题目
牛牛早上起床一看#xff0c;自己睡过了#xff0c;赶紧起床准备去学校#xff0c;他去学校只有两种方式#xff0c;坐公交车和步行#xff0c;牛牛去学校是一条直线#xff0c;这条直线上总共有 nnn 个车站#xff0c;车站之间的距离都是相等的自己睡过了赶紧起床准备去学校他去学校只有两种方式坐公交车和步行牛牛去学校是一条直线这条直线上总共有 nnn 个车站车站之间的距离都是相等的每个车站只有一种公交车aia_iai每个公交车只在对应的公交站停车每个公交车的速度也不一样第 iii 种公交车过一站的时间需要 tit_iti并且公交车是单向行驶只能从左到到右走路可以任意走然而牛牛自己步行走一站需要的时间为 TTT恰好牛牛家和学校都在某一个站点分别为 sss 和 ttt问最少需要多少时间牛牛才能到学校
分析
直接建图跑最短路注意公交车是单向的而人可以双向行走
代码
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includerandom
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
mt19937 rnd(233);
typedef long long ll;
typedef pairint,int pii;
const int mod1e97;
const int N100010;
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_queuepii,vectorpii,greaterpii q;q.push({0,start});while(q.size()){int tq.top().second;q.pop();if(st[t]) continue;st[t]1;for(int ih[t];i!-1;ine[i]){int je[i];if(dist[j]dist[t]w[i]) {dist[j]dist[t]w[i];q.push({dist[j],j});}}if(t1n) {if(dist[t1]dist[t]T){dist[t1]dist[t]T;q.push({dist[t1],t1});}}if(t-10){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);cinnmstT;for(int i1;im;i) cincost[i];for(int i1;in;i){int a;cina;if(last[a]) add(last[a],i,cost[a]);last[a]i;}coutdijkstra(s,t)\n;return 0;
}
