“呼！！终于到了，可是接下来要怎么走才能到达楚楚街港港呢？”亮亮在醋溜港直发愁。
突然“啾”的一下，一只银色小船出现在亮亮的面前，上面坐着小精灵丹丹“又见面了，有什么可以帮助你的么？”小精灵向亮亮眨了眨眼睛，微笑着说。
“我想去楚楚街港，但我不知道要怎么走，请问你可以告诉我么？”亮亮按捺着激动的心情轻声问道。
“楚楚街港呀......那是个特别美好的地方”小精灵歪着头想了想，说“我只能告诉你大海上所有的航线，剩下的就只能靠你自己啦~”
“只有所有的航线呀”，亮亮的内心再三挣扎，却又没有其他的办法。 “不管有多困难，我一定要达到楚楚街港，请你告诉我吧”亮亮坚定地对小精灵说。
小精灵欣赏地点了点头，递给亮亮一张航线图，并叮嘱道“时限是1000天，一定要到哦~”，然后如来时一般“啾”的一声，消失了。 亮亮现在迫切地想要抵达楚楚街港，请问亮亮最快能在第几天抵达楚楚街港呢？
[编程题]航线
- 热度指数：1938 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
一行包含两个整数N(2<=N<=500),M(1<=M<=2000)，用单个空格隔开。表示公有N个港，M条航线。起点为1，终点为N。 接下来M行，每行包含五个整数P,Q(1<=P,Q<=n), K(1<=K<=1000), X,Y(0<=X,Y<=10000),代表P,Q两个港有航线并需要K天，并且该航线在第X天到第Y天天气恶劣不可通行。
输出描述:
一个整数，即亮亮最快能在第几天抵达楚楚街港
示例1
输入
4 4
2 1 1 7 13
4 3 2 10 11
1 3 8 9 12
2 3 3 2 10
输出
14
这不是和上一题一样用Dijkstra算法么
就是要多考虑一下风暴的问题
若行船时间要与风暴时间有重合需要等到暴风雨结束才能出发
AC代码如下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
const int maxn = 500 + 5;
int dp[maxn], taken[maxn], n, m;
struct Node{
int x, y, val, start, end;
Node(int a, int b, int c, int d, int e){
x = a; y = b; val = c; start = d; end = e;
}
};
vector<Node> v[maxn];
int main(){
while(scanf("%d%d", &n, &m) == 2){
memset(dp, 0, sizeof(dp));
memset(taken, 0, sizeof(taken));
for(int i = 0; i < m; i++){
int a, b, c, d, e;
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
Node n1(a, b, c, d, e);
Node n2(b, a, c, d, e);
v[a].push_back(n1);
v[b].push_back(n2);
}
for(int i = 0; i <= n; i++) dp[i] = INT_MAX;
dp[1] = 0;
for(int k = 0; k < n; k++){
int min_dp = INT_MAX, min_i;
for(int i = 1; i <= n; i++)
if(!taken[i] && dp[i] < min_dp)
min_dp = dp[min_i = i];
taken[min_i] = 1;
for(int i = 0; i < v[min_i].size(); i++){
Node n = v[min_i][i];
if(dp[n.x]>=n.end || (dp[n.x]+n.val)<n.start);//暴风雨来临前已经溜了或者暴风雨刮完了才到
dp[n.y] = min(dp[n.y], dp[n.x] + n.val);
else dp[n.y] = min(dp[n.y], n.end + n.val);//要等暴风雨结束才能走
}
}
cout<<dp[n] + 1<<endl;//天数是从第一天开始算的 没有第0天 所以加一
for(int i = 0; i <= n; i++) v[i].clear();
}
return 0;
}
编辑于 2018-10-24 19:02:10
回复(0)
//可100%通过
//迪杰斯特拉最短路径求解，注意的是算下一步cost的时候要根据当前的时间来计算
//输出的结果比较坑，不知道为什么要吧算出来的结果+1才能通过？按道理
//给的例子在第13天就可以到的
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <limits>
#include <set>
using namespace std;
struct Edge
{
int cost;
int noBegin;
int noEnd;
Edge()
{
cost = -1;
}
};
int main()
{
int n,m;
while(cin>>n>>m)
{
vector<vector<Edge>> graph(n+1,vector<Edge>(n+1,Edge()));
while(m--)
{
int a1,a2,a3,a4,a5;
cin>>a1>>a2>>a3>>a4>>a5;
graph[a1][a2].cost = a3;
graph[a1][a2].noBegin=a4;
graph[a1][a2].noEnd=a5;
graph[a2][a1]=graph[a1][a2];
}
vector<int> dist(n+1,std::numeric_limits<int>::max());
set<int> visited;
dist[1]=0;
while(visited.count(n)==0)
{
int min_index = -1;
int minV = std::numeric_limits<int>::max();
for(int i=1;i<=n;i++)
{
if(!visited.count(i) && dist[i]<minV)
{
min_index=i;
minV = dist[i];
}
}
visited.insert(min_index);
for(int i=1;i<=n;i++)
{
if(graph[min_index][i].cost>0 && !visited.count(i))
{
int &cur = dist[min_index];
Edge & temp = graph[min_index][i];
int actual;
if(cur+temp.cost<temp.noBegin || cur+1>temp.noEnd)
actual = cur+temp.cost;
else actual = temp.noEnd+temp.cost;
if(actual < dist[i])dist[i] = actual;
}
}
}
cout<<dist[n]+1<<endl;
}
return 0;
}
编辑于 2016-08-24 17:50:23
回复(4)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;
struct route{ int x,y; int k; route() { k = MAX; }
};
int Dijkstra(int n, vector<vector<route>> &R)
{ vector<int> T(n+1,MAX); for(int i=1;i<=n;i++) if(R[1][i].k != MAX) if(R[1][i].k < R[1][i].x) T[i] = R[1][i].k; else T[i] = R[1][i].y + R[1][i].k; R[1][1].k = 1; for(int p=1;p<=n;p++) { int Min = MAX; int j = -1; for(int i=1;i<=n;i++) if(R[i][i].k!=1 && T[i]<Min) { Min = T[i]; j = i; } if(j == -1) break; else{ R[j][j].k = 1; for(int i=1;i<=n;i++) { if(R[i][i].k != 1) { int t; if(R[j][i].k+T[j]<R[j][i].x || T[j]+1>R[j][i].y) t = T[j] + R[j][i].k; else t = R[j][i].y + R[j][i].k; if(t < T[i]) T[i] = t; } } } } return T[n]+1;
}
int main()
{ int n,m; cin>>n>>m; vector<vector<route>> R(n+1, vector<route>(n+1)); for(int i=0;i<m;i++) { int a,b,k,x,y; cin>>a>>b>>k>>x>>y; R[a][b].k = k; R[a][b].x = x; R[a][b].y = y; R[b][a] = R[a][b]; } cout<<Dijkstra(n, R)<<endl; return 0;
}
发表于 2017-12-26 01:50:51
回复(0)
#include<stdio.h>
#include<vector>
using namespace std;
#define INF 1005
struct route{
int x,y;
int k; //routes[i][j] 表示从i港口到j港口需要k天，其中第x到第y天禁止通行
route(){
k = INF;
}
};
int dijstra(int n, vector<vector<route>> &routes){
vector<int> time(n+1, INF); //time[i] 表示从1号港口到i号港口需要几天
for(int i = 1; i <= n; i++){
if(routes[1][i].k != INF){
if(routes[1][i].k < routes[1][i].x){
time[i] = routes[1][i].k; //初始化time数组
}
else time[i] = routes[1][i].y + routes[1][i].k;
}
}
routes[1][1].k = 1;
for(int p = 1; p <= n; p++){
int min = INF;
int j = -1;
for(int i = 1; i <= n; i++){
if(routes[i][i].k != 1 && time[i] < min){
min = time[i];
j = i;
}
}
if(j == -1) break;
else{
routes[j][j].k = 1;
for(int i = 1; i <= n; i++){
if(routes[i][i].k != 1){
int temp;
if(routes[j][i].k+time[j] < routes[j][i].x || time[j]+1 > routes[j][i].y){
//行程中没有遇到恶劣天气
temp = time[j] + routes[j][i].k;
}
else temp =routes[j][i].y + routes[j][i].k;
if(temp < time[i]) time[i] = temp;
}
}
}
}
return time[n]+1;
}
int main(){
int n, m,p,q,k,x,y;
scanf("%d%d", &n,&m);
vector<vector<route>> routes(n+1, vector<route>(n+1));
for(int i = 0; i < m; i++){
scanf("%d%d%d%d%d", &p, &q, &k, &x, &y);
routes[p][q].k = k;
routes[p][q].x = x;
routes[p][q].y = y;
routes[q][p] = routes[p][q];
}
printf("%d\n", dijstra(n, routes));
}
思路：dijkstra算法更新路径最短时间时，要注意禁止通行时间（多加一个判断条件），直接算最短路径有错，楼上已分析。
最后结果要加1，我不明白。
编辑于 2016-08-26 19:22:29
回复(1)
Dijkstra算法求解单源最短路径问题，需要注意的是在计算两点之间距离的时候，需要结合
实际考虑天气因素，出发的时候不能有恶劣天气吧，海上航行的时候不能遇到恶劣天气吧，
即要保证从某点出发时算起，到达到下一个目的地的这段时间为止，不能和恶劣天气的区间
有重叠。如果有重叠怎么办呢？只能等到恶劣天气结束才能出发。这样两点之间的实际距离
= 恶劣天气的结束时间 + 两点之间理论距离，按照题目中"到达"的含义，到达时间为次日，
所以距离还要再 + 1。以点 x 与 y 之间的行程估算为例：
如果未来风平浪静：dist[y] = dist[x] + length[x][y]
如果遇到恶劣天气：dist[y] = (x,y)这段路的恶劣天气结束时间 + length[x][y] + 1
#include <iostream>
#include <vector>
using namespace std;
#define MAX 1001
bool allow(int start1, int end1, int start2, int end2){
if (end1 < start2 || end2 < start1)
return true;
else
return false;
}
int main(){
int N, M;
cin >> N >> M;
vector<vector<int>> length(N + 1, vector<int>(N + 1, MAX));
vector<vector<pair<int, int>>> forbid(N + 1, vector<pair<int, int>>(N + 1));
for (int i = 0; i < M; i++){
int P, Q, K, X, Y;
cin >> P >> Q >> K >> X >> Y;
length[P][Q] = K;
length[Q][P] = K;
forbid[P][Q].first = X;
forbid[P][Q].second = Y;
forbid[Q][P].first = X;
forbid[Q][P].second = Y;
}
vector<int> dist(N + 1);
vector<bool> find(N + 1, false);
dist[1] = 1; find[1] = true;
for (int i = 2; i <= N; i++){
if (!allow(dist[1], dist[1] + length[1][i] - 1, forbid[1][i].first, forbid[1][i].second))
dist[i] = forbid[1][i].second + length[1][i] + 1;
else
dist[i] = dist[1] + length[1][i];
}
for (int i = 2; i <= N; i++){
int min = MAX;
int x = 0;
for (int t = 2; t <= N; t++){
if (!find[t] && dist[t] < min){
min = dist[t];
x = t;
}
}
find[x] = true;
for (int y = 2; y <= N; y++){
if (!find[y]){
int tempdist = dist[x] + length[x][y];
if (!allow(dist[x], dist[x] + length[x][y] - 1, forbid[x][y].first, forbid[x][y].second))
tempdist = forbid[x][y].second + length[x][y] + 1;
if (tempdist < dist[y])
dist[y] = tempdist;
}
}
}
cout << dist[N] << endl;
return 0;
}
编辑于 2018-03-24 19:09:15
回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;
struct edge{
int to;
int cost;
int noStart;//不可通行的起始天
int noEnd;//不可通行的结束天
edge(int x,int y,int z,int t):to(x),cost(y),noStart(z),noEnd(t){}
};
const int maxn = 10000;
int m,n;
vector<edge*> graph[maxn];//下标从1开始
vector<int> d(10000,2147483647);
vector<int> vis(10000,0);
int needTime(int nowTime,int endTime,int noStart,int noEnd){
if((nowTime>=noStart && nowTime<=noEnd) ||(endTime>=noStart && endTime<=noEnd) || (endTime>=noEnd && nowTime<=noStart)){
return noEnd + (endTime-nowTime)+1;
}
else{
return endTime;
}
}
void Dijistra(){
d[1] = 0;//初始化第一个节点
vis[1]=1;
for(int i=0;i<graph[1].size();i++){//确定第一个顶点的邻接点的距离
d[graph[1][i]->to] = needTime(d[1],d[1]+graph[1][i]->cost,graph[1][i]->noStart,graph[1][i]->noEnd);//需要的天数加上去
}
for(int i=0;i<n;i++){//一次循环确定一个顶点的最短距离
int minV=2147483647,minI;
for(int j=1;j<=n;j++){//找出目前未访问过且距离源点最小的点，下标从1开始
if(!vis[j] && d[j] < minV){
minV = d[j];
minI = j;
}
}
vis[minI] = 1;//把这个点加入到集合中
for(int j=0;j<graph[minI].size();j++){//对该点的邻接点遍历
int temp = needTime(d[minI],d[minI]+graph[minI][j]->cost,graph[minI][j]->noStart,graph[minI][j]->noEnd);
d[graph[minI][j]->to] = min(d[graph[minI][j]->to],temp);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){//读入所有数据
int a[5];
for(int j=0;j<5;j++)
cin>>a[j];
edge* e1 = new edge(a[1],a[2],a[3],a[4]);
edge* e2 = new edge(a[0],a[2],a[3],a[4]);
graph[a[0]].push_back(e1);
graph[a[1]].push_back(e2);
}
Dijistra();
cout<<d[n];
return 0;
}
最后有个用例过不去-_-
发表于 2020-06-28 20:41:44
回复(0)
其实也是在网上看到的别人的讲解
import java.util.Arrays;
import java.util.Scanner;
//在无向图中从 1 到 n 最短路径
public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int map[][] = new int[n+1][n+1];
for (int i = 0;i < n+1;i++){ // 初始化所有点相互不可达为 -1
for (int j = 0;j < n+1;j++){
map[i][j] = -1;
}
}
int[][] s = new int[n+1][n+1]; //点不可达的起始时间
int[][] e = new int[n+1][n+1]; //点不可达的终止时间
for (int i = 0;i < m;i++){
int p = sc.nextInt();
int q = sc.nextInt();
int k = sc.nextInt();
int x = sc.nextInt();
int y = sc.nextInt();
map[p][q] = k; //两个港有航向则两个点双向可达，边的大小为时间
map[q][p] = k;
s[p][q] = x;
s[q][p] = x;
e[p][q] = y;
e[q][p] = y;
}
System.out.println(dijkstra(map,s,e,n));
}
/*
* DijStra是求最短路径的算法，算法步骤：
* 初识集合只包括一个圆点V，然后把距离V最小的点U加入集合，再把距离距离u最小的点加入集合，如此递归，知道所有点都在集合中
* */
private static int dijkstra(int[][] map, int[][] s, int[][] e, int n) {
int[] dist = new int[n+1];
boolean[] vis = new boolean[n+1];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[1] = 0;
for (int i = 1;i <= n;i++){
int min = Integer.MAX_VALUE;
int v = 1;
for (int j = 1;j <= n;j++){ //找到下一个点
if (!vis[j] && dist[j] < min){
min = dist[j];
v=j;
}
}
vis[v] = true;
for (int k = 1;k <= n;k++){
if (!vis[k] && map[v][k] != -1){
int tmp = dist[v] + map[v][k];
if (tmp < s[v][k]){ //在不可达的时间前到达了
dist[k] = Math.min(tmp,dist[k]);
}else { //在不可达的市价段内到达
if (dist[v] > e[v][k]){ //在前往k前已经过了不可达时间
dist[k] = Math.min(tmp,dist[k]);
}else { // 在不通行的时间范围内到达，则只能暴风雨过后在出发
dist[k] = Math.min(dist[k],e[v][k]+map[v][k]);
}
}
}
}
}
return dist[n]+1;//dist[n]为到达n需要几天，答案是第几天
}
}
发表于 2020-06-13 20:17:46
回复(0)
#include<bits/stdc++.h>
using namespace std;
struct cmp{
bool operator()(pair<int,int>& a,pair<int,int>& b)
{
return a.first>b.first;
}
};
struct node{
int v;
int cost;
int nobegin;
int noend;
//node():cost(INT_MAX){}
node(int v_,int cost_,int x,int y):v(v_),cost(cost_),nobegin(x),noend(y){}
};
void dijkstra(vector<vector<node>>& graph,vector<int>& d,int s)
{
d[s] = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
pq.push({0,s});
while(!pq.empty())
{
auto it = pq.top();pq.pop();
if(it.first>d[it.second]) continue;
int k = it.second;
for(int i=0;i<graph[k].size();++i)
{
int w = d[k]+graph[k][i].cost;
int tmp;
if(w<graph[k][i].nobegin || d[k]>=graph[k][i].noend)
{
tmp = w;
}
else{
tmp = graph[k][i].cost + graph[k][i].noend;
}
if(tmp<d[graph[k][i].v])
{
d[graph[k][i].v] = tmp;
pq.push({tmp,graph[k][i].v});
}
}
}
}
int main()
{
// 堆优化dijkstra
int N,M;
while(cin>>N>>M)
{
vector<vector<node>>graph(N+1,vector<node>());
for(int i=1;i<=M;++i)
{
int a,b,cost,nobegin,noend;
cin>>a>>b>>cost>>nobegin>>noend;
graph[a].push_back(node(b,cost,nobegin,noend));
graph[b].push_back(node(a,cost,nobegin,noend));
}
vector<int>d(N+1,INT_MAX);
dijkstra(graph,d,1);
cout<<d[N]+1<<endl;
}
return 0;
}
发表于 2020-04-18 11:53:25
回复(0)
#include <iostream>
using namespace std;
const int MAXV = 1000; //本题的顶点数为500，还不算大。
const int INF = 1000000000; //设INF是一个很大的数。
int g[MAXV][MAXV]; //图
bool vit[MAXV] = { false }; //记录是否访问
int d[MAXV]; //记录最短距离
struct node {
int qi1;
int end1;
};
node g1[MAXV][MAXV]; //记录风暴信息，看，就是加个数组的事。
void Dijkstra(int s,int n) {
d[s] = 0;
vit[s] = true;
for (int i = 1; i < n; i++) {
int u = -1; int MIN = INF;
for (int j = 1; j < n; j++) {
if(vit[j]==false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if (u == -1) { return; }
vit[u] = true;
for (int v = 1; v < n; v++) {
if (vit[v]==false&&g[u][v]!=0) {
//在这里需要单独更新一下边的权值，因为这里叠加了风暴的因素，因此是动态的权值。
if ((d[u] >= g1[u][v].qi1 - g[u][v]) && (d[u] <= g1[u][v].end1)) { g[u][v] = g1[u][v].end1 - d[u] + g[u][v]; }
else {}
if (d[u] + g[u][v] < d[v]) {
d[v] = d[u] + g[u][v];
}
}
}
}
}
int main() {
int N, M;
cin >> N >> M;
fill(d, d + MAXV, INF); //先置为最大值
for (int i = 0; i < M; i++) {
int a, b, c, d1, e;
cin >> a >> b >> c >> d1 >> e;
g[a][b] = g[b][a] = c;
g1[a][b].qi1 = d1;
g1[b][a].qi1 = d1;
g1[a][b].end1 = e;
g1[b][a].end1 = e;
//这个地方是先把与1相连的边，先给初始化。
if (a == 1) {
if (d1 > c) { d[b] = c;}
else { d[b] = e+c; }
}
if (b == 1) {
if (d1 > c) { d[a] = c; }
else { d[a] = e+c; } //权值就是它风暴结束的那一天+渡河需要的时间
}
}
Dijkstra(1,N+1);
cout << d[N]+1;
return 0;
}
编辑于 2020-03-04 21:29:24
回复(0)
以下细节仅针对于天数是从 1 开始计算的，如果从 0 开始还需要做一下调整。
注意一下几个细节：
1. 遇到风暴开船时间为 y_i + 1.
2. 双向边 (不过不建双向边样例过不去)。
3. 判断从 u 到 v 的时候会不会遇上风暴时，我们认为当在第 x 天风暴来袭恰好到达 v 是允许的。换句话说就是风暴时间区间是左开右闭 (题意也没说清，不过忽略这条样例也过不去)。
#include <bits/stdc++.h>
#define QAQ 0x3f3f3f3f
using namespace std;
struct jj
{
int v,next,c,x,y;
}w[4000];
struct kk
{
int v,dis;
bool operator<(const struct kk x)const
{
return dis>x.dis;
}
};
int h[500],numw,a[500];
void insert(int u,int v,int c,int x,int y)
{
w[numw].v=v;
w[numw].c=c;
w[numw].x=x;
w[numw].y=y;
w[numw].next=h[u];
h[u]=numw++;
}
int dij(int s,int t)
{
int dis[5000],i;
struct kk pre;
priority_queue<struct kk>q;
memset(dis,QAQ,sizeof(dis));
dis[0]=1;
q.push(kk{0,dis[0]});
while(q.empty()==0)
{
pre=q.top();
q.pop();
for(i=h[pre.v];i!=-1;i=w[i].next)
{
int add;
if(dis[pre.v]+w[i].c-1<w[i].x||dis[pre.v]>w[i].y)
{
add=dis[pre.v];
}
else
{
add=w[i].y+1;
}
if(dis[w[i].v]>add+w[i].c)
{
dis[w[i].v]=add+w[i].c;
q.push(kk{w[i].v,dis[w[i].v]});
}
}
}
return dis[t];
}
int main()
{
int n,m,i,u,v,x,y,c;
scanf("%d %d",&n,&m);
numw=0;
memset(h,-1,sizeof(h));
for(i=0;m>i;i++)
{
scanf("%d %d %d %d %d",&u,&v,&c,&x,&y);
insert(u-1,v-1,c,x,y);
insert(v-1,u-1,c,x,y);
}
printf("%d",dij(0,n-1));
return 0;
}
编辑于 2019-04-07 14:04:34
回复(0)
Python
try:
while 1:
import collections
N,M =[int(x) for x in input().split()]
G = collections.defaultdict(dict)
for i in range(M):
s,e,c,a,b = [int(x) for x in input().split()]
G[s][e] = [c,a,b]
G[e][s] = [c,a,b]
ans = [float('inf') for i in range(N+1)]
ans[1] = 1
book = set()
remain = set([i for i in range(N+1)])
minv = 1
while len(book)<len(G.keys()):
book.add(minv)
remain.remove(minv)
for temp_node in G[minv]:
if temp_node in book:
continue
if ans[minv]+G[minv][temp_node][0]<=G[minv][temp_node][1]:
if ans[minv]+G[minv][temp_node][0]<ans[temp_node]:
ans[temp_node] = ans[minv] + G[minv][temp_node][0]
elif ans[minv]>G[minv][temp_node][2]:
if ans[minv]+G[minv][temp_node][0]<ans[temp_node]:
ans[temp_node] = ans[minv] + G[minv][temp_node][0]
else:
if G[minv][temp_node][2]+G[minv][temp_node][0]+1<ans[temp_node]:
ans[temp_node] = G[minv][temp_node][2] + G[minv][temp_node][0]+1
temp_add_node = float('inf')
for i in remain:
if ans[i]<temp_add_node:
minv = i
temp_add_node = ans[i]
print(ans[-1])
except EOFError:
pass
发表于 2018-07-11 10:19:46
回复(0)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <limits.h>
using namespace std;
struct node
{
int dest;
int cost;
int inv[2] = { 0 };
node(int _d, int _c, int _in1, int _in2) :dest(_d), cost(_c) { inv[0] = _in1; inv[1] = _in2; };
};
int main()
{
int n, m;
while (cin >> n >> m)
{
int p, q, k, x, y;
vector<vector<node>> book(n + 1);
for (int i = 0; i<m; i++)
{
cin >> p >> q >> k >> x >> y;
node n1(q, k, x, y);
node n2(p, k, x, y);
book[p].push_back(n1);
book[q].push_back(n2);
}
vector<int> tm(n + 1, INT_MAX);
set<int> vist;
vist.insert(1);
tm[1]=0;
for (int i = 0; i<book[1].size(); i++)
{
int ds = book[1][i].dest;
int dt = book[1][i].cost;
if (tm[1]+ dt<book[1][i].inv[0])
tm[ds]= dt;
else if (book[1][i].inv[1] + dt <= 1000)
tm[ds]= book[1][i].inv[1] + dt;
}
while (vist.find(n) == vist.end())
{
int mini = INT_MAX;
int sig;
for (int j = 0; j<n + 1; j++)
{
if(vist.find(j)!=vist.end())
continue;
if (tm[j]<mini)
{
sig = j;
mini = tm[j];
}
}
vist.insert(sig);
for (int p = 0; p<book[sig].size(); p++)
{
int ds = book[sig][p].dest;
int dt = book[sig][p].cost;
if (tm[sig]>book[sig][p].inv[1]||tm[sig]+dt<book[sig][p].inv[0])
tm[ds] = min(dt+tm[sig],tm[ds]);
else if (book[sig][p].inv[1]+dt<= 1000)
tm[ds] = min(book[sig][p].inv[1]+dt,tm[ds]);
}
}
cout << tm[n]+1 << endl;
}
}
//多谢牛客上的大佬分析代码给我这种跨专业菜鸡学习，这种题终于能自己跑出来了，感激不尽
发表于 2018-05-13 10:53:23
回复(0)
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define X first
#define Y second
#define forl(i, s, e) for (int i = s; i < e; i++)
using route = struct _Route {
int dest;
int time;
int forbids;
int forbide;
};
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
vector<route> routes[501];
forl(i, 1, N+1) {
routes[i] = vector<route>();
}
forl(i, 0, M) {
int src;
route r;
route r2;
cin >> src >> r.dest >> r.time >> r.forbids >> r.forbide;
r2 = r;
r2.dest = src;
routes[src].push_back(r);
routes[r.dest].push_back(r2);
}
queue<int> q;
q.push(1);
int result[N+1];
forl(i, 0, N+1)
result[i] = INT_MAX;
result[1] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (route r: routes[cur]) {
if (result[cur] + r.time < r.forbids ||
result[cur] > r.forbide) {
if (r.time + result[cur] < result[r.dest]) {
q.push(r.dest);
result[r.dest] = result[cur] + r.time;
}
} else if (r.forbide + r.time < result[r.dest]) {
q.push(r.dest);
result[r.dest] = r.forbide + r.time;
}
}
}
cout << result[N] + 1 << '\n';
return 0;
}
发表于 2017-09-08 17:51:19
回复(0)
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define INF 2000
struct Node{
int x, y;
int k;
Node() {
k = INF;
}
};
int main() {
int N, M,result;
while (cin >> N >> M) {
vector<vector<Node>> map(N+1, vector<Node>(N+1));
for (int i = 0;i < M;i++) {
int p, q, k, x, y;
cin >> p >> q >> k >> x >> y;
map[p][q].x = x;
map[p][q].y = y;
map[p][q].k = k;
map[q][p] = map[p][q];
}
vector<int> visted(N + 1,0), cost(N + 1,INF);
for (int i = 1;i < N + 1;i++) {
if (map[1][i].k != INF) {
if (map[1][i].k < map[1][i].x)
cost[i] = map[1][i].k;
else
cost[i] = map[1][i].y + map[1][i].k;
}
}
cost[1] = 0;
for (int i = 2;i < N+1;i++) {
int min = INF,pos;
for (int j = 1;j < N + 1;j++) {
if (visted[j] == 0 && cost[j] < min) {
min = cost[j];
pos = j;
}
}
visted[pos] = 1;
for (int j = 1;j < N + 1;j++) {
if (visted[j] == 0) {
int temp;
if (((map[pos][j].k + cost[pos]) < map[pos][j].x) || (cost[pos] + 1 > map[pos][j].y))
temp = cost[pos] + map[pos][j].k;
else
temp = map[pos][j].y + map[pos][j].k;
if (temp < cost[j]) {
cost[j] = temp;
}
}
}
}
cout << cost[N] + 1 << endl;
}
return 0;
}
发表于 2017-06-11 16:00:51
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct line{
line(int _Q, int _K, int _X, int _Y): Q(_Q), K(_K), X(_X), Y(_Y) {}
int Q, K, X, Y;
};
int main() {
int N, M;
while(cin >> N >> M) {
unordered_map<int, vector<line>> umap;
for(int i = 0; i < M; ++i) {
int P, Q, K, X, Y;
cin >> P >> Q >> K >> X >> Y;
line linePoint(Q-1, K, X, Y);
line relinePoint(P-1, K, X, Y);
umap[P-1].push_back(linePoint);
umap[Q-1].push_back(relinePoint);
}
// Dijkstra INIT
//int dist[N];
//memset(dist, INF, sizeof(dist));
vector<int> dist(N, INF);
for(int i = 0; i < umap[0].size(); ++i) {
if(umap[0][i].K < umap[0][i].X) {
dist[umap[0][i].Q] = umap[0][i].K;
} else {
dist[umap[0][i].Q] = umap[0][i].K + umap[0][i].Y;
}
}
set<int> noselect;
for(int i = 1; i < N; ++i) noselect.insert(i);
while (noselect.size() > 0) {
int minDays = INF, loc = -1;
for(auto &i : noselect) {
if(dist[i] < minDays) {
minDays = dist[i];
loc = i;
}
}
noselect.erase(loc);
for(auto &pos : noselect) {
for(auto &item : umap[pos]) {
if(dist[item.Q] < item.Y && item.K + dist[item.Q] >= item.X) {
dist[pos] = min(dist[pos], item.Y + item.K);
} else {
dist[pos] = min(dist[pos], dist[item.Q] + item.K);
}
}
}
}
cout << dist[N-1] + 1 << endl;
}
return 0;
}
发表于 2017-05-08 17:19:09
回复(0)
#include<iostream>
#include<vector>
#include<limits>
#include<set>
#include<algorithm>
using namespace std;
const int MAXINT = numeric_limits<int>::max();
struct data
{
data(int z, int a, int b, int c){
q=z;
k = a;
x = b;
y = c;
}
int q;
int k;
int x;
int y;
};
int main(){
int N, M;
while (cin >> N >> M){
vector<vector<data> >graph(N+1);//图
int p, q, k, x, y;
for (int i = 0; i < M; i++){
cin >> p >> q >> k >> x >> y;
graph[p].push_back(data(q,k, x, y));
graph[q].push_back(data(p, k, x, y));
}
vector<int > dp(N+1, MAXINT);//到达第j个港口的最短时间
set<int> visited;
visited.insert(1);
dp[1] = 0;
int st = dp[1];
int ed = dp[1];
for (int i = 0; i < graph[1].size(); i++){
st = dp[1];
ed = graph[1][i].k + st;
if (st>graph[1][i].y||ed<graph[1][i].x){
dp[graph[1][i].q] = ed;
}
else {
st = graph[1][i].y;//等一段时间再走
ed = graph[1][i].k + st;
dp[graph[1][i].q] = ed;
}
}
while (visited.count(N) == 0){
//寻找能到的最近的点
int minK = MAXINT;
int id = -1;
for (int i = 1; i <= N; i++){
if (!visited.count(i)){
if (dp[i] < minK){
minK = dp[i];
id = i;
}
}
}
visited.insert(id);//放入集合
//探测下一步能到达的点,如果都不能到就休息
for (int i = 0; i < graph[id].size(); i++){
st = dp[id];
ed = graph[id][i].k + st;
if (st>graph[id][i].y||ed<graph[id][i].x){//不需要等待
dp[graph[id][i].q] = min(dp[graph[id][i].q], ed);
}
else{
st = graph[id][i].y;
ed = graph[id][i].k + st;
dp[graph[id][i].q] = min(dp[graph[id][i].q], ed);
}
}
}
cout << dp[N]+1 << endl;
}
return 0;
}
为毛最后要+1啊 理解不能
发表于 2017-04-16 12:07:58
回复(1)
import java.util.Scanner;
class Line{
public Line(){
visited=false;
time=Integer.MAX_VALUE;
}
public void set(int t,int b,int e){
this.begin=b;
this.end=e;
this.time=t;
}
boolean visited;
int begin;
int end;
int time;
}
public class Main{
public static int dijkstra(Line[][] lines,int n) {
int[] time=new int[n+1];
for (int i=2;i<=n;i++) {
if(lines[1][i].time<lines[1][i].begin)
time[i]=lines[1][i].time;
else
time[i]=lines[1][i].time+lines[1][i].end;
}
time[1]=1;
lines[1][1].visited=true;
int v=1;
while (v!=n) {
int minTime=Integer.MAX_VALUE;
v=1;
for(int j=1;j<=n;j++)
{
if(!lines[j][j].visited&&time[j]<minTime)
{
minTime=time[j];
v=j;
}
}
lines[v][v].visited=true;
for(int j=2;j<=n;j++)
{
if(!lines[j][j].visited&&lines[v][j].time<Integer.MAX_VALUE){
int tmp;
if(lines[v][j].time+time[v]<lines[v][j].begin||time[v]>lines[v][j].end)
{
tmp=lines[v][j].time+time[v];
}
else
tmp=lines[v][j].end+lines[v][j].time;
time[j]=time[j]<tmp?time[j]:tmp;
}
}
}
return time[n]+1;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
int n=sc.nextInt();
int m=sc.nextInt();
Line[][] lines=new Line[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
lines[i][j]=new Line();
}
}
for (int i=0;i<m;i++) {
int p=sc.nextInt();
int q=sc.nextInt();
int t=sc.nextInt();
int b=sc.nextInt();
int e=sc.nextInt();
lines[p][q].set(t,b,e);
lines[q][p]=lines[p][q];
}
System.out.println(dijkstra(lines,n));
}
}
}
发表于 2017-02-23 15:42:21
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt(),
m = sc.nextInt();
int[] max = new int[n];
int[][] routes = new int[n][n];
int[][][] avail = new int[n][n][2];
for (int i = 0;i < m;i++){
int start = sc.nextInt() - 1,
end = sc.nextInt() - 1,
cost = sc.nextInt(),
x = sc.nextInt(),
y = sc.nextInt();
if (x > y){
int tmp = x;
x = y;
y = tmp;
}
routes[start][end] = cost;
routes[end][start] = cost;
avail[start][end][0] = x;
avail[start][end][1] = y;
avail[end][start][0] = x;
avail[end][start][1] = y;
}
max[0] = 1;
getMax(max, routes, n, n -1, avail);
System.out.println(max[n - 1] + 1);
}
}
public static void getMax(int[] max, int[][] route, int len, int dest, int[][][] avail){
ArrayList<Integer> queue = new ArrayList<>();
queue.add(0);
while (!queue.isEmpty()){
int tmp = queue.remove(0);
for (int i = 1;i < len;i++){
if (route[tmp][i] > 0){
int sum = max[tmp] + route[tmp][i];
int x = avail[tmp][i][0],
y = avail[tmp][i][1];
if (!(max[tmp] >= y || sum <= x)){
sum = y + route[tmp][i];
}
if (max[i] == 0 || max[i] > sum){
max[i] = sum;
queue.add(i);
}
}
}
}
}
}
只过了90%的点，不知道错在哪里，求各位大大解惑。
基本思路，利用Dijkstra算法结合不能出行的时间进行判断。
发表于 2016-10-15 15:55:49
回复(1)
通过90%,最后一组case获取不到，没法调试了，请大神看一下哪里有问题。
思路：SPFA求最短路径
#include <iostream> #include <vector> #include <queue> using namespace std; struct line{ int end; int spent; int fib_start; int fib_end; line(int e, int s, int fs, int fe) :end(e), spent(s), fib_start(fs), fib_end(fe) {} line() :end(-1), spent(0), fib_start(0), fib_end(0) {} }; vector<vector<line> > table; int main() { int N, M; cin >> N >> M; table.resize(N); int P, Q, K, X, Y; for (int i = 0; i < M; ++i) { cin >> P >> Q >> K >> X >> Y; table[P - 1].push_back(line(Q - 1, K, X, Y)); table[Q - 1].push_back(line(P - 1, K, X, Y)); } queue <int> q; vector<int> days(N, 0x3F3F3F3F); days[0] = 0; vector<bool> visited(N, false); q.push(0); visited[0] = 1; while (!q.empty()) { int x; x = q.front(); q.pop(); visited[x] = false; for (int k = 0; k < table[x].size(); ++k) { int y = table[x][k].end; int spent = table[x][k].spent; int fib_start = table[x][k].fib_start; int fib_end = table[x][k].fib_end; int padding = 0; if ( (days[x] >= fib_start && days[x] <= fib_end) || (days[x] + spent >= fib_start && days[x] + spent <= fib_end)|| (days[x] <= fib_start && days[x] + spent >= fib_end) ) { padding = fib_end + 1 - days[x]; } if (days[x] + spent + padding < days[y]) { days[y] = days[x] + spent + padding; if (!visited[y]) { visited[y] = true; q.push(y); } } } } cout << days[N-1] << endl; }
发表于 2016-07-20 17:18:37
回复(0)
#include <stdio.h>
#include <stdlib.h>
int edges[4000][8];
int border[501];
int distance[501];
int mark[501];
int compare(const void *a, const void *b){
int *ia = (int*)a, *ib = (int*)b;
if(ia[0] == ib[0]){
return ia[1] - ib[1];
}else{
return ia[0] - ib[0];
}
}
int main(){
int N, M;
scanf("%d%d", &N, &M);
int realM = 0;
for(int i = 0; i < M; i++){
int P,Q,K,X,Y;
scanf("%d%d%d%d%d", &P, &Q, &K, &X, &Y);
if(P!=Q){
edges[realM][0] = P;
edges[realM][1] = Q;
edges[realM][2] = K;
edges[realM][3] = X;
edges[realM++][4] = Y;
edges[realM][0] = Q;
edges[realM][1] = P;
edges[realM][2] = K;
edges[realM][3] = X;
edges[realM++][4] = Y;
}
}
qsort(edges, realM, sizeof(int) * 8, compare);
int j = 1;
border[0] = 0;
for(int curr = 0; curr < realM; curr++){
for(;j < edges[curr][0]; j++){
border[j] = curr;
}
}
for(; j <= N; j++){
border[j] = realM;
}
for(int i = 1; i <= N; i++){
distance[i] = 0x7fffffff;
}
distance[1] = 0;
for(int j = 1; j <= N; j++){
int minv = 0x7fffffff, mini;
for(int i = 1; i <= N; i++){
if(!mark[i] && distance[i] < minv){
minv = distance[i];
mini = i;
}
}
mark[mini] = 1;
for(int j = border[mini - 1]; j < border[mini]; j++){
if(!mark[edges[j][1]]){
int newd = minv + edges[j][2];
if(newd >= edges[j][3] && minv <= edges[j][4]){
newd = edges[j][4] + 1 + edges[j][2];
}
if(newd < distance[edges[j][1]]){
distance[edges[j][1]] = newd;
}
}
}
}
printf("%d\n", distance[N]);
return 0;
}
有个测试例是坏的，搞毛啊
发表于 2016-07-08 19:43:48
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
