1450
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "ladder.in" #define OUTPUT_FILE "ladder.out" vector< vector< pair<int, int> > > E; vector< int > vd; vector< int > r; list<int> T; list<int> L; void topsort() { for(int i = 0; i < E.size(); i++) { if(vd[i] == 0) { T.push_back(i); } } while(T.size() != 0) { int v = T.front(); T.pop_front(); L.pb(v); for(int i = 0; i < E[v].size(); i++) { vd[E[v][i].first]--; if(vd[E[v][i].first] == 0) T.pb(E[v][i].first); } } } void findpath() { while(L.size() != 0 ) { int v = L.front(); L.pop_front(); if(r[v] == INT_MIN) continue; for(int i = 0; i < E[v].size(); i++) { if(r[E[v][i].first] == INT_MIN) { r[E[v][i].first] = r[v] + E[v][i].second; } else { r[E[v][i].first] = max(r[E[v][i].first], r[v] + E[v][i].second); } } } } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int N,M; cin >> N >> M; E.resize(N); vd.resize(N); r.resize(N); for(int i = 0; i < N; i++) r[i] = INT_MIN; for(int i = 0; i < M; i++) { int a,b,d; cin >> a >> b >> d; E[a-1].pb(mp(b-1,d)); vd[b-1]++; } int S,F; cin >> S >> F; topsort(); r[S-1] = 0; findpath(); if(r[F-1] == INT_MIN) { cout << "No solution"; } else { cout << r[F-1]; } return 0; }
page revision: 0, last edited: 18 Dec 2007 19:55