Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define NM 105
- #define mp make_pair
- #define pii pair <int,int>
- using namespace std;
- ifstream f("firma.in");
- ofstream g("firma.out");
- int n,m,d[NM];
- vector <pii> v[NM];
- set <pii> heap;
- void Dijkstra(int nod)
- { for(int i=1; i<=n; i++)
- d[i]=(1<<30);
- heap.insert(mp(0,nod));
- d[nod]=0;
- while(!heap.empty())
- { int nod=(*heap.begin()).second;
- heap.erase(heap.begin());
- vector <pii> :: iterator it;
- for(it=v[nod].begin(); it!=v[nod].end(); it++)
- { int nodV=(*it).first,cost=(*it).second;
- if(d[nod]+cost<d[nodV])
- { if(d[nodV]!=(1<<30))
- heap.erase(heap.find(mp(d[nodV],nodV)));
- heap.insert(mp(cost+d[nod],nodV));
- d[nodV]=cost+d[nod];
- }
- }
- }
- }
- int main()
- { f>>n>>m;
- while(m--)
- { int x,y,val;
- f>>x>>y>>val;
- v[x].push_back(mp(y,val));
- v[y].push_back(mp(x,val));
- }
- int sMin=(1<<30),iMin=0;
- for(int i=1; i<=n; i++)
- { Dijkstra(i);
- int s=0;
- for(int i=1; i<=n; i++)
- s+=d[i];
- if(s<sMin)
- { sMin=s;
- iMin=i;
- }
- }
- g<<iMin;
- f.close(); g.close(); return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement