/**
* footing
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#include <unordered_set>
#include <limits>
using namespace std;
typedef vector<vector<pair<int, int>>> alist;
typedef unordered_set<int> set;
typedef priority_queue<pair<long long, int>> heap; // contiene prima la lunghezza del percorso, poi il nodo successivo
struct edge {
int u;
int v;
int weight;
};
void dfs(alist &graph, set &explored, int start) {
explored.insert(start);
for (auto beg = graph[start].begin(); beg != graph[start].end(); ++beg) {
if (explored.find(beg->first) == explored.end()) {
dfs (graph, explored, beg->first);
}
}
}
long long dijkstra(alist &graph, int start, int end)
{
auto n = graph.size();
set nodes(n);
dfs(graph, nodes, start); // ignora nodi irraggiungibili
vector<long long> lengths(n, -1);
set explored(n);
heap greedy_scores;
explored.insert(start);
lengths[start] = 0;
for (auto beg = graph[start].begin(); beg != graph[start].end(); ++beg) {
if (beg->first != end) { // ignora collegamento diretto tra start e end
greedy_scores.push(make_pair(-(lengths[start] + beg->second), -beg->first));
}
}
while (explored != nodes) {
auto prossimo = greedy_scores.top();
greedy_scores.pop();
prossimo.first = -prossimo.first; prossimo.second = -prossimo.second;
if (explored.find(prossimo.second) == explored.end()) {
explored.insert(prossimo.second);
lengths[prossimo.second] = prossimo.first;
for (auto beg = graph[prossimo.second].begin(); beg != graph[prossimo.second].end(); ++beg) {
if (explored.find(beg->first) == explored.end() && !((prossimo.second == start && beg->first == end) || (prossimo.second == end && beg->first == start))) { // condizione necessaria a ignorare ogni volta il collegamento diretto
greedy_scores.push(make_pair(-(lengths[prossimo.second] + beg->second), -beg->first)); // un meno era andato perso
}
}
}
}
return lengths[end];
}
int main()
{
ifstream in("input.txt");
int n, m; in >> n >> m;
alist graph(n);
vector<edge> edges;
for (int i = 0; i < m; ++i) { // scritto n invece che m
int u, v, w;
in >> u >> v >> w;
--u; --v;
graph[u].push_back(make_pair(v, w));
graph[v].push_back(make_pair(u, w));
edge e;
e.u = u;
e.v = v;
e.weight = w;
edges.push_back(e);
}
in.close()
//for (auto beg = graph.begin(); beg != graph.end(); ++beg) {
//cout << beg - graph.begin() << ": ";
//for (auto beg2 = beg->begin(); beg2 != beg->end(); ++beg2) {
//cout << beg2->first << " " << beg2->second << ", ";
//}
//cout << "\n";
//}
//cout << "\n";
long long min = numeric_limits<long long>::max();
for (auto e = edges.begin(); e != edges.end(); ++e) {
long long shortest = dijkstra(graph, e->u, e->v);
cout << shortest + e->weight << "\n";
if (shortest + e->weight < min) {
min = shortest + e->weight;
}
}
ofstream out("output.txt");
out << min << endl;
out.close();
}
Salve ragazzi avrei bisogno di aiuto con questo problema.
Il mio algoritmo totalizza soltanto 30/100 e non passa i test case 1, 4, 6, 7, 8, e 9 per timeout, mentre per il 5 l’esecuzione è fermata con segnale 11.
L’algoritmo consiste nell’applicare dijkstra una volta per ogni arco, con partenza da un nodo dell’arco e arrivo all’altro, tutto questo ignorando l’arco corrente, che non viene mai inserito nell’heap, in modo da calcolare la lunghezza del ciclo minimo.
La lista di adiacenza che uso ha questa struttura:
0: (1, 1) (3, 2) (4, 5)
1: (0, 1) (2, 2) (4, 6) (5, 4)
2: (1, 2) (4, 1) (3, 7) (5, 3)
3: (4, 2) (0, 2) (2, 7)
4: (1, 6) (3, 2) (2, 1) (0, 5)
5: (1, 4) (2, 3)
dove ogni indice corrisponde a un nodo, e ad ogni nodo c’è un vettore di nodi collegati e il rispettivo peso (questa è quella per il caso di esempio).
Devo aggiungere che il codice di dijkstra usato qui passa tutti i casi di test del problema dijkstra anche senza considerare l’arco che colega direttamente partenza e arrivo, e non sono sicuro del perchè.
Forse nei test case di dijkstra partenza e destinazione non sono mai collegate direttamente?