警察设置了路障以检查过往车辆用英语怎么说

发布网友 发布时间：2022-05-03 08:58

我来回答

共3个回答

懂视网 时间：2022-05-03 13:19

输入描述

输入文件的第(1) 行为两个整数，(N) 和 (R)，用空格隔开；

第(2....R+1) 行：每行包含三个用空格隔开的整数 (A)、(B) 和(D) ，表示存在一条长度为(D(1 leq D leq 5000)) 的路连接农场 (A)和农场(B) 。

输出格式

输出仅一个整数，表示从农场(1) 到农场(N) 的第二短路的长度。

样例输入

4 4
1 2 100
2 4 200
2 3 250
3 4 100

样例输出

450

思路

用Dijkstra计算最短路径，因为要求求出严格次短路径，所用用两个数组记录，一个记录最短路径一个记录此段路经，跑Dijkstra即可

/****************************************************
/@Author: Kirito
/@TIME: 2020-04-30
/@FILENAME: Roadblocks.cpp
/@REMARK: 
/****************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn=211111;
//graph
int first[maxn],nxt[maxn],u[maxn],v[maxn],w[maxn];
int n,m,cnt;
//spfa-box
int dis[maxn],book[maxn],ans[maxn];
//邻接表
void add(int x,int y,int d){
 cnt++;
 u[cnt]=x;v[cnt]=y;w[cnt]=d;
 nxt[cnt]=first[u[cnt]];first[u[cnt]]=cnt;
 return;
}
//Dijkstra
void Dijkstra(){
 CSE(dis,INF);CSE(book,0);CSE(ans,INF);
 priority_queue<pii,vector<pii>,greater<pii>> box;
 box.push(make_pair(0,1));dis[1]=0;
 while(!box.empty()){
 int x=box.top().second,base=box.top().first;box.pop();
 for(int i=first[x];i!=-1;i=nxt[i]){
  int y=v[i];
  int d=w[i]+base;
  if(dis[y]>d){
  ans[y]=dis[y];
  dis[y]=d;
  box.push(make_pair(dis[y],y));
  }
  else if(dis[y]==d) continue;
  else if(ans[y]>d){
  ans[y]=d;
  box.push(make_pair(ans[y],y));
  }
 }
 }
 return ;
}

int main()
{
#ifndef ONLINE_JUDGE
 freopen("in.in","r",stdin);
#endif
 FAST;
 CSE(first,-1);CSE(nxt,-1);CSE(w,INF);
 cin>>n>>m;
 for(int i=0;i<m;i++){
 int x,y,d;
 cin>>x>>y>>d;
 add(x,y,d);add(y,x,d);
 }
 Dijkstra();
 cout<<ans[n]<<endl;
 return 0;
}

Roadblocks

标签：make   continue   出现   lowbit   结束   with   旅行   online   book   

热心网友 时间：2022-05-03 10:27

热心网友 时间：2022-05-03 11:45