PAT : 数据结构与算法题目集(中文)7-9 旅游规划
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3F3F3F3F;
struct ints
{
int Aim, length, cost;
};
int getdigit(void)
{
int temp{0};
char ch;
while (1)
{
ch = getchar();
if (ch == ' ' || ch == '\n' || ch == '\n')
return temp;
temp = temp * 10 + ch - '0';
}
}
void putdigit(int temp)
{
if (temp >= 10)
putdigit(temp / 10);
putchar('0' + (temp % 10));
}
void Dijkstra(vector<vector<ints>> Graph, int A, int B)
{
vector<int> dist(Graph.size(), INF);
vector<int> cost(Graph.size());
vector<bool> book(Graph.size());
dist[A] = 0;
while (1)
{
int Index{-1}, Min{INF};
int Size = dist.size();
for (int i = 0; i != Size; ++i)
if (!book[i] && dist[i] < Min)
{
Min = dist[i];
Index = i;
}
if (Index == -1)
{
putdigit(dist[B]);
putchar(' ');
putdigit(cost[B]);
putchar('\n');
return;
}
book[Index] = true;
for (const auto &i : Graph[Index])
{
if (!book[i.Aim])
{
if (dist[Index] + i.length < dist[i.Aim])
{
dist[i.Aim] = dist[Index] + i.length;
cost[i.Aim] = cost[Index] + i.cost;
}
else if (dist[Index] + i.length == dist[i.Aim] &&
cost[Index] + i.cost < cost[i.Aim])
cost[i.Aim] = cost[Index] + i.cost;
}
}
}
}
int main(int argc, char *argv[])
{
int vertex{getdigit()}, edge{getdigit()}, A{getdigit()}, B{getdigit()};
vector<vector<ints>> graph(vertex);
while (edge--)
{
int a{getdigit()}, b{getdigit()}, length{getdigit()}, cost{getdigit()};
graph[a].push_back({b, length, cost});
graph[b].push_back({a, length, cost});
}
Dijkstra(graph, A, B);
return EXIT_SUCCESS;
}
一道很好的Dijkstra算法测试题~
>>单调队列优化的Dijkstra
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
using pairint = pair<int, int>;
const int INF = 0x3F3F3F3F;
struct ints
{
int Aim, length, cost;
};
struct Compare
{
bool operator()(pairint a, pairint b)
{
return a.second > b.second;
}
};
int getdigit(void)
{
int temp{0};
char ch;
while (1)
{
ch = getchar();
if (ch == ' ' || ch == '\n' || ch == '\n')
return temp;
temp = temp * 10 + ch - '0';
}
}
void putdigit(int temp)
{
if (temp >= 10)
putdigit(temp / 10);
putchar('0' + (temp % 10));
}
void Dijkstra(vector<vector<ints>> Graph, int A, int B)
{
vector<int> dist(Graph.size(), INF);
vector<int> cost(Graph.size());
vector<bool> book(Graph.size());
priority_queue<pairint, vector<pairint>, Compare> pq;
dist[A] = 0;
pq.push({A, dist[A]});
while (!pq.empty())
{
pairint temp = pq.top();
pq.pop();
book[temp.first] = true;
for (const auto &i : Graph[temp.first])
{
if (!book[i.Aim])
{
if (dist[temp.first] + i.length < dist[i.Aim])
{
dist[i.Aim] = dist[temp.first] + i.length;
cost[i.Aim] = cost[temp.first] + i.cost;
}
else if (dist[temp.first] + i.length == dist[i.Aim] &&
cost[temp.first] + i.cost < cost[i.Aim])
cost[i.Aim] = cost[temp.first] + i.cost;
else
continue;
pq.push({i.Aim, dist[i.Aim]});
}
}
}
putdigit(dist[B]);
putchar(' ');
putdigit(cost[B]);
putchar('\n');
}
int main(int argc, char *argv[])
{
int vertex{getdigit()}, edge{getdigit()}, A{getdigit()}, B{getdigit()};
vector<vector<ints>> graph(vertex);
while (edge--)
{
int a{getdigit()}, b{getdigit()}, length{getdigit()}, cost{getdigit()};
graph[a].push_back({b, length, cost});
graph[b].push_back({a, length, cost});
}
Dijkstra(graph, A, B);
return EXIT_SUCCESS;
}
耗时和未优化的差不多,题目并不是稀疏图……