L3-007 天梯地图 (30 分)(两次dijkstra)

68 阅读 0 评论 45 点赞

我是靠谱客的博主优美母鸡，最近开发中收集的这篇文章主要介绍L3-007 天梯地图 (30 分)(两次dijkstra)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一种dijkstra算法而已。（套路，利用prev放到queue里面作为答案）
如果这两条路线是完全一样的，简单queue比较即可。（简单问题）

#include "bits/stdc++.h"
using namespace std;
int from, dist;
int len_table[600][600];
int len_prev[600];
int len_dis[600];
int len_point[600];
int len_vis[600];
int tim_table[600][600];
int tim_vis[600];
int tim_len[600];
int tim_prev[600];
int tim_dis[600];
queue<int> len_ans, tim_ans;
void len_getans(int i){
if(i == -1) return;
len_getans(len_prev[i]);
len_ans.push(i);
}
void tim_getans(int i){
if(i == -1) return;
tim_getans(tim_prev[i]);
tim_ans.push(i);
}
bool queue_cmp(queue<int> a, queue<int> b){
if(a.size() != b.size()) return false;
else{
while(!a.empty()){
if(a.front() != b.front()) return false;
a.pop();
b.pop();
}
return true;
}
}
int main(){
memset(len_point, 0x3f, 2400);
memset(len_dis, 0x3f, 2400);
memset(len_table, 0x3f, 2400 * 600);
memset(tim_table, 0x3f, 2400 * 600);
memset(len_vis, 0, 2400);
memset(tim_vis, 0, 2400);
memset(tim_len, 0x3f, 2400);
memset(tim_dis, 0x3f, 2400);
int pn, n;
scanf("%d %d", &pn, &n);
int p1, p2, one_way, length, time;
for(int i = 0; i < n; ++i){
scanf("%d %d %d %d %d", &p1, &p2, &one_way, &length, &time);
len_table[p1][p2] = length;
tim_table[p1][p2] = time;
if(!one_way) {
len_table[p2][p1] = length;
tim_table[p2][p1] = time;
}
}
scanf("%d %d", &from, &dist);
//
len_point[from] = 1;
len_dis[from] = 0;
len_prev[from] = -1;
while(true){
int p = -1;
int short_dis = 0x3f3f3f3f;
for(int i = 0; i < pn; ++i){
if(short_dis > len_dis[i] && !len_vis[i]){
short_dis = len_dis[i];
p = i;
}
}
if(p == -1) break;
len_vis[p] = 1;
for(int i = 0; i < pn; ++i){
if(0x3f3f3f3f != len_table[p][i] && len_dis[i] >= len_dis[p] + len_table[p][i]){
if(len_dis[i] > len_dis[p] + len_table[p][i] ||
(len_dis[i] == len_dis[p] + len_table[p][i] && len_point[i] > len_point[p] + 1)
){
len_dis[i] = len_dis[p] + len_table[p][i];
len_point[i] = len_point[p] + 1;
len_prev[i] = p;
}
}
}
}
tim_len[from] = 0;
tim_prev[from] = -1;
tim_dis[from] = 0;
while(true){
int p = -1;
int mintime = 0x3f3f3f3f;
for(int i = 0; i < pn; ++i){
if(tim_dis[i] < mintime && !tim_vis[i]){
mintime = tim_dis[i];
p = i;
}
}
if(p == -1) break;
tim_vis[p] = 1;
for(int i = 0; i < pn; ++i){
if(0x3f3f3f3f != tim_table[p][i] && tim_table[p][i] + tim_dis[p] <= tim_dis[i]){
if(tim_table[p][i] + tim_dis[p] < tim_dis[i] ||
(tim_table[p][i] + tim_dis[p] == tim_dis[i] && tim_len[p] + len_table[p][i] < tim_len[i])){
tim_len[i] = tim_len[p] + len_table[p][i];
tim_prev[i] = p;
tim_dis[i] = tim_table[p][i] + tim_dis[p];
}
}
}
}
//
tim_getans(dist);
len_getans(dist);
if(queue_cmp(len_ans, tim_ans)){
printf("Time = %d; Distance = %d: ", tim_dis[dist], len_dis[dist]);
int len_cnt = 0;
while(!len_ans.empty()){
if(len_cnt) printf(" => ");
printf("%d", len_ans.front());
len_ans.pop();
len_cnt++;
}
return 0;
}
printf("Time = %d: ", tim_dis[dist]);
int tim_cnt = 0;
while(!tim_ans.empty()){
if(tim_cnt) printf(" => ");
printf("%d", tim_ans.front());
tim_ans.pop();
tim_cnt++;
}
printf("nDistance = %d: ", len_dis[dist]);
int len_cnt = 0;
while(!len_ans.empty()){
if(len_cnt) printf(" => ");
printf("%d", len_ans.front());
len_ans.pop();
len_cnt++;
}
return 0;
}