首页 > 代码库 > luogu P1186 玛丽卡
luogu P1186 玛丽卡
题目描述
麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。
因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。
在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。
麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。
玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。
编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。
输入输出格式
输入格式：第一行有两个用空格隔开的数N和M，分别表示城市的数量以及城市间道路的数量。1≤N≤1000，1≤M≤N*(N-1)/2。城市用数字1至N标识，麦克在城市1中，玛丽卡在城市N中。
接下来的M行中每行包含三个用空格隔开的数A，B和V。其中1≤A，B≤N，1≤V≤1000。这些数字表示在A和城市B中间有一条双行道，并且在V分钟内是就能通过。
输出格式：输出文件的第一行中写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。
输入输出样例
输入样例#1：
5 71 2 81 4 102 3 92 4 102 5 13 4 73 5 10
输出样例#1：
27
heap优化Dijkstra先求出无障碍最短路，
再枚举当最短路上某一段障碍时情况
#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define INF 0x3f3f3f3f#define N 1020int n,m;int head[N];int dis[N];struct nnode{ int v;int w,next;}edge[N*N/2];struct node{ int v,dis; friend bool operator < (node a,node b){ return a.dis>b.dis; }}cur;priority_queue<node>q;int read() { int x=0,f=1; char c; while (c<‘0‘ || c>‘9‘) {if(c==‘-‘)f = -1;c = getchar();} while (c>=‘0‘ && c<=‘9‘)x=x*10+c-‘0‘,c=getchar(); return x*f;}int num = 0;void add_edge(int x,int y,int w){ edge[num].v=y; edge[num].w=w; edge[num].next=head[x]; head[x]=num++;}int pre_now[N];int pre[N];int Dijkstra(int p,int tp){ //memset (head,-1,sizeof -1); memset (dis,0x3f,sizeof dis); dis[1] = 0; q.push(node{1,0}); while(!q.empty()) { cur = q.top(); q.pop(); if(dis[cur.v]<cur.dis)continue; int u = cur.v; for (int i = head[u];i != -1;i = edge[i].next) { int v = edge[i].v; if((v == p && u== tp) || (v==tp && p == u))continue; if(dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; pre_now[v]=u; q.push((node){v,dis[v]}); } } } return dis[n];}int main() { n = read(); m = read(); for(int i=1;i<=n;i++)head[i]=-1; for (int i = 1; i <= m; i++){ int a,b,c; a = read(),b = read(),c = read(); add_edge(a,b,c);add_edge(b,a,c); } int ans=Dijkstra(0,0); memcpy(pre,pre_now,sizeof(pre)); int k=n; while(k) { int tmp = Dijkstra(pre[k],k); if(tmp!=INF) ans = max(ans,tmp); k = pre[k]; } printf("%d\n",ans); return 0;}
luogu P1186 玛丽卡
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。