Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdio>
- #include <queue>
- #include <climits>
- #include <algorithm>
- #define MAXN 1005
- using namespace std;
- typedef pair<int,int> ii;
- typedef vector<ii> vi;
- vi G[MAXN];
- int N, M, dist[MAXN], prec[MAXN], minimo=INT_MAX;
- bool precU[MAXN], vis[MAXN];
- int prossimoNodo(){ //per i grafi non connessi, trova il prossimo nodo non ancora visitato
- int i;
- for(i=1; i<=N && vis[i]; i++);
- return i;
- }
- int main(){
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- cin >> N >> M;
- for(int i=0, u, v, w; i<M; i++){
- cin >> u >> v >> w;
- G[u].push_back( make_pair(w, v) );
- G[v].push_back( make_pair(w, u) );
- }
- priority_queue< ii, vi, greater<ii> > Q;
- fill_n(dist, N+1, INT_MAX);
- fill_n(prec, N+1, N);
- dist[0]=prec[0]=0;
- int nd;
- while((nd=prossimoNodo())<=N){ //trova il prossimo nodo da cui far partire Dijkstra
- dist[nd] = 0; //distanza iniziale a 0
- Q.push( make_pair(0, nd) ); //inserisco il nodo di partenza nell'heap
- prec[nd] = 0; //precedente iniziale a 0
- while(!Q.empty()){
- int u = Q.top().second; Q.pop(); //prendo il nodo da visitare
- if(vis[u]) continue; //se l'ho già visitato salto al prossimo
- for(int i=0; i<G[u].size(); i++){ //vedo i nodi connessi ad "u"
- int v = G[u][i].second, w = G[u][i].first;
- if( vis[v] && v!=prec[u]){ //se ce n'è uno che è già visitato ma non è il predecessore, vedo se può essere un ciclo minimo
- //Trovo il predecessore comune
- fill_n(precU, N+1, false);
- int p = prec[u], d;
- while(p>0){
- precU[p]=true;
- p = prec[p];
- }
- p = prec[v];
- while(p>0 && !precU[p])
- p = prec[p];
- //ora il predecessore comune sarà "p"
- if(p==0) p=nd;
- //la lunghezza del ciclo sarà la DistanzaDaPadU + DistanzaDaPaV + ArcoDaUaV
- d = dist[u]-dist[p] + dist[v]-dist[p] + w;
- minimo = min(d, minimo);
- }
- if( w+dist[u] < dist[v]){ //Classico controllo di Dijkstra
- dist[v] = w+dist[u];
- prec[v] = u;
- Q.push( make_pair(dist[v], v) );
- }
- }
- vis[u] = true; //segno il nodo come visitato
- }
- }
- cout << minimo << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement