Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int int64_t
- #define ii pair<int, int>
- #define fi first
- #define se second
- using namespace std;
- const int MAX = 1e3+6;
- const int MX = 1e15;
- int n, d[4][MAX], m1, m2, st, en, f[5][MAX], vs[5][MAX], dp[MAX][MAX];
- std::vector<ii> g[3][MAX];
- int res;
- void Dijkstra(int num){
- for(int i=1; i<=n; i++) d[num][i] = MX;
- priority_queue<ii, vector<ii>, greater<ii> > pq;
- d[num][en] = 0;
- pq.push(ii(0, en));
- while (!pq.empty()){
- int u = pq.top().se, du = pq.top().fi; pq.pop();
- if (du != d[num][u]) continue;
- for(int i=0; i< g[num][u].size() ; i++){
- int v = g[num][u][i].se, uv = g[num][u][i].fi;
- if (du + uv < d[num][v]){
- d[num][v] = du + uv;
- pq.push(ii(d[num][v], v));
- }
- }
- }
- }
- void BFS(){
- queue<ii> q;
- q.push(ii(st, 1));
- while (!q.empty()){
- int u = q.front().fi, type = q.front().se; q.pop();
- // cout << u << "\n";
- for(int i=0; i<(int) g[type][u].size(); i++){
- int v = g[type][u][i].se, uv = g[type][u][i].fi;
- if (d[type][v] < d[type][u]){
- // cout << u << " " << v << "\n";
- if (vs[u][v]){
- res = -1;
- return;
- }
- if (f[type][u] + uv > f[3-type][v]){
- f[3-type][v] = f[type][u] + uv;
- vs[u][v] = true;
- q.push(ii(v, 3-type));
- }
- }
- }
- }
- }
- void DFS(int u, int type){
- vs[type][u] = 1;
- for(int i=0; i<(int)g[type][u].size(); i++){
- int v = g[type][u][i].se;
- if (d[type][v] >= d[type][u]) continue;
- if (vs[3-type][v]==2) continue;
- if (vs[3-type][v]==1) {
- res = -1;
- return;
- continue;
- }
- // if (u==1 && v==4) cout << "SF\n";
- DFS(v, 3-type);
- }
- vs[type][u] = 2;
- }
- int DP(int u, int type){
- if (u == en) return 0;
- if (dp[u][type] != -1) return dp[u][type];
- dp[u][type] = -99999999999;
- // cout << u << " ";
- for(int i=0; i< g[type][u].size(); i++){
- int v = g[type][u][i].se, uv = g[type][u][i].fi;
- if (d[type][v] < d[type][u]){
- dp[u][type] = max(dp[u][type], DP(v, 3-type) + uv);
- }
- }
- return dp[u][type];
- }
- signed main(int argc, char const *argv[])
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- // #ifndef ONLINE_JUDGE
- // freopen("input.txt","r",stdin);
- // #endif
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("TOUR.INP","r",stdin);
- freopen("TOUR.OUT","w",stdout);
- #endif
- cin >> n >> st >> en;
- cin >> m1;
- for(int i=1; i<=m1; i++){
- int u, v, w;
- cin >> u >> v >> w;
- g[1][u].push_back(ii(w, v));
- g[1][v].push_back(ii(w, u));
- }
- cin >> m2;
- for(int i=1; i<=m2; i++){
- int u, v, w;
- cin >> u >> v >> w;
- g[2][u].push_back(ii(w, v));
- g[2][v].push_back(ii(w, u));
- }
- Dijkstra(1);
- Dijkstra(2); // en
- // cout << -1;
- // return 0;
- // BFS();
- memset(dp, -1, sizeof dp);
- DFS(st, 1);
- // cout << "XO";
- if (res==-1) {
- cout << res;
- return 0;
- }
- // DP(en, 1);
- // DP(en, 2);
- cout << DP(st, 1);
- // cout << max(f[1][en], f[2][en]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement