Title translation:
It is to find the shortest path from one point to another point.
However, due to many restrictions, it has to be calculated twice, so it is very complicated to write.
Question solution ideas:
You can use dijkstra or dfs. If you use the latter, the last test point may time out.
Code:
dfs (last test point timed out):
#include<bits/stdc + + .h>
using namespace std;
int N, M;//Number of nodes, number of edges
vector<int> v[501];
int dis[501][501];
int cost[501][501];
int mindis[501];
int min_len = INT_MAX, min_cost = INT_MAX;
vector<int> path1, path2, temp;
int so, des;
int temp_cost = INT_MAX;
void dfs(int curnode, int curlen, int curcost)
{
if (curlen > mindis[curnode]) return;
else
mindis[curnode] = curlen;
temp.push_back(curnode);
if (curnode == des)
{
if (curlen < min_len)
{
min_len = curlen;
path1 = temp;
temp_cost = curcost;
}
if (curlen == min_len & amp; & amp;curcost<temp_cost)
path1 = temp;
}
else {
for (auto i : v[curnode])
dfs(i, curlen + dis[curnode][i], curcost + cost[curnode][i]);
}
temp.pop_back();
}
void dfs2(int curnode, int curlen)
{
if (curlen > mindis[curnode]) return;
else
mindis[curnode] = curlen;
temp.push_back(curnode);
if (curnode == des)
{
if (curlen < min_cost)
{
min_cost = curlen;
path2 = temp;
}
if (curlen == min_cost & amp; & temp.size() < path2.size())
path2 = temp;
}
else {
for (auto i : v[curnode])
dfs2(i, curlen + cost[curnode][i]);
}
temp.pop_back();
}
int main()
{
cin >> N >> M;
int q, w, e, r, t;
for (int i = 0;i < M;i + + )
{
cin >> q >> w >> e >> r >> t;
if (e)//One-way
{
v[q].push_back(w);
dis[q][w] = r;
cost[q][w] = t;
}
else//bidirectional
{
v[q].push_back(w);
v[w].push_back(q);
dis[q][w] = dis[w][q] = r;
cost[q][w] = cost[w][q] = t;
}
}
for (int i = 0;i < 501;i + + )
mindis[i] = INT_MAX;
cin >> so >> des;
dfs(so, 0, 0);
for (int i = 0;i < 501;i + + )
mindis[i] = INT_MAX;
temp.clear();
dfs2(so, 0);
if (path1 != path2)
{
cout << "Distance = " << min_len << ":";
for (int i = 0;i < path1.size();i + + )
{
if(i)
cout << " ->";
cout << " " << path1[i];
}
cout << endl;
}
else
cout << "Distance = " << min_len << "; ";
cout << "Time = " << min_cost << ":";
for (int i = 0;i < path2.size();i + + )
{
if(i)
cout << " ->";
cout << " " << path2[i];
}
}
dijkstra (AC, reprinted in AC code)
#include<bits/stdc + + .h>
using namespace std;
int n, m, source, dest, min_distance, min_time;
vector<int> ans_t, ans_d, dpre(500, -1), tpre(500, -1);
vector<vector<int>> times(500, vector<int>(500, -1)), distances(500, vector<int>(500, -1)), graph(500,vector<int>(500, 0));
void dfs1(int x){
if(x == -1) return;
dfs1(dpre[x]);
ans_d.push_back(x);
}
void dfs2(int x){
if(x == -1) return;
dfs2(tpre[x]);
ans_t.push_back(x);
}
void dijkstra1(int beg){
vector<int> lowcost(500, 0x3f3f3f3f), vis(500, 0), dtime(500, 0x3f3f3f3f);
lowcost[beg] = 0;
dpre[beg] = -1;
for (int i = 0; i < n;i + + ){
int Min = 0x3f3f3f3f, k = -1;
for (int j = 0; j < n; j + + ){
if(vis[j] == 0 & amp; & amp; lowcost[j] < Min){
Min = lowcost[j];
k = j;
}
}
if(k == -1) break;
vis[k] = 1;
for (int j = 0; j < n; j + + ){
if(vis[j] == 0 & amp; & amp; graph[j][k] == 1){
//If the conditions are met, update the information. Pay attention to the logic short circuit phenomenon here.
if(lowcost[j] > lowcost[k] + distances[j][k] || (lowcost[j] == lowcost[k] + distances[j][k] & amp; & amp; dtime[k] + times[k][j] < dtime[j])){
dpre[j] = k;
dtime[j] = dtime[k] + times[k][j];
lowcost[j] = lowcost[k] + distances[j][k];
}
}
}
}
min_distance = lowcost[dest];
dfs1(dest);
}
void dijkstra2(int beg){
vector<int> lowcost(500, 0x3f3f3f3f), vis(500, 0), intersections(500, 0x3f3f3f3f);
lowcost[beg] = 0;
tpre[beg] = -1;
for (int i = 0; i < n;i + + ){
int Min = 0x3f3f3f3f, k = -1;
for (int j = 0; j < n; j + + ){
if(vis[j] == 0 & amp; & amp; lowcost[j] < Min){
Min = lowcost[j];
k = j;
}
}
if(k == -1) break;
vis[k] = 1;
for (int j = 0; j < n; j + + ){
if(vis[j] == 0 & amp; & amp; graph[j][k] == 1){
if(lowcost[j] > lowcost[k] + times[j][k] || (lowcost[j] == lowcost[k] + times[j][k] & amp; & amp; intersections[k] + 1 < intersections[j])){
tpre[j] = k;
intersections[j] = intersections[k] + 1;
lowcost[j] = lowcost[k] + times[j][k];
}
}
}
}
min_time = lowcost[dest];
dfs2(dest);
}
int main(){
int s, e, a, l, t, isSame = 1;
cin >> n >> m;
for (int i = 0; i < m;i + + ){
cin >> s >> e >> a >> l >> t;
graph[s][e] = graph[e][s] = 1;
times[s][e] = times[e][s] = t;
distances[s][e] = distances[e][s] = l;
}
cin >> source >> dest;
dijkstra1(source);
dijkstra2(source);
if(ans_d.size() == ans_t.size()){
for (int i = 0; i < ans_t.size();i + + ){
if(ans_t[i] != ans_d[i]){
isSame = 0;
break;//Save some time if you can
}
}
}else
isSame = 0;
if(isSame == 0){
printf("Distance = %d: %d", min_distance, ans_d[0]);
for (int i = 1; i < ans_d.size();i + + )
printf(" -> %d", ans_d[i]);
printf("\
Time = %d: %d", min_time, ans_t[0]);
for (int i = 1; i < ans_t.size();i + + )
printf(" -> %d", ans_t[i]);
}else{
printf("Distance = %d; Time = %d: %d", min_distance, min_time, ans_t[0]);
for (int i = 1; i < ans_t.size();i + + )
printf(" -> %d", ans_t[i]);
}
cout << endl;
return 0;
}
Pitfalls:
Test point 4 may time out when using dfs