Letöltés: mb_futar.cpp #include <cstdio> #include <cstdlib> #include <algorithm> #include <list> #include <queue> #include <vector> #define INF 100000000 using namespace std; int n, m, h; struct csucs_struct { int id; int dist; bool done; list<int> to; list<int> weight; }; csucs_struct* csucsok; class csucs_compare { public: bool operator() (const int& p1, const int& p2) const { return csucsok[p1].dist>csucsok[p2].dist; } }; void beolvas() { FILE* reader = fopen("futar.be8", "r"); fscanf(reader, "%d %d %d", &n, &m, &h); h--; csucsok = new csucs_struct[n]; for(int i=0; i<n; i++) { csucsok[i].id=i; csucsok[i].dist=INF; csucsok[i].done=false; } int t1, t2, t3; for(int i=0; i<m; i++) { fscanf(reader, "%d %d %d", &t1, &t2, &t3); t1--; t2--; csucsok[t1].to.push_back(t2); csucsok[t1].weight.push_back(t3); } } int main() { beolvas(); csucsok[h].dist=0; priority_queue<int, vector<int>, csucs_compare> pq; pq.push(h); while(!pq.empty()) { int top=pq.top(); pq.pop(); if(csucsok[top].done) continue; list<int>::iterator it_weight=csucsok[top].weight.begin(); for(list<int>::iterator it_to=csucsok[top].to.begin(); it_to!=csucsok[top].to.end(); it_to++) { int alt=csucsok[top].dist+*it_weight; if(alt<csucsok[*it_to].dist) { csucsok[*it_to].dist=alt; pq.push(*it_to); } it_weight++; } csucsok[top].done=true; } int mmax=0; for(int i=0; i<n; i++) printf("%d\n", csucsok[i].dist); for(int i=0; i<n; i++) mmax=max(mmax, csucsok[i].dist); printf("Sol: %d", mmax); } |