Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Murad Eynizade */
- #include <bits/stdc++.h>
- #define int long long
- #define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
- #define F first
- #define S second
- using namespace std;
- const int sz = 1001;
- int n , m , x , y , w , s , t , used[sz][3] , d[sz][3];
- vector< pair<int,int> >v[sz][3];
- bool f = false;
- priority_queue< pair<int,int> >pq;
- void dijkstra(int s,int di) {
- for (int i = 1;i<=n;i++)d[i][di] = 1000000000000000LL;
- d[s][di] = 0;
- pq.push({0 , s});
- while (!pq.empty()) {
- int u = pq.top().S;
- pq.pop();
- for (auto to : v[u][di]) {
- if (d[to.F][di] > d[u][di] + to.S) {
- d[to.F][di] = d[u][di] + to.S;
- pq.push({-d[to.F][di] , to.F});
- }
- }
- }
- }
- void dfs(int s,int di) {
- if (f)return;
- if (s == t)return;
- used[s][di] = 1;
- for (auto to : v[s][di]) {
- if (f)return;
- if (d[to.F][di] < d[s][di]) {
- assert(s != t);
- if (used[to.F][3 - di] == 1 && to.F != t) {
- f = true;
- return;
- }
- if (used[to.F][3 - di] == 0)dfs(to.F , 3 - di);
- }
- }
- used[s][di] = 2;
- }
- int ans[sz][3];
- int solve(int s,int di) {
- if (ans[s][di] != -1)return ans[s][di];
- int mx = -1000000000000000LL;
- for (auto to : v[s][di]) {
- if (d[to.F][di] < d[s][di]) mx = max(mx , to.S + solve(to.F , 3 - di));
- }
- ans[s][di] = mx;
- return mx;
- }
- main()
- {
- FAST_READ;
- cin>>n>>s>>t;
- cin>>m;
- while (m--) {
- cin>>x>>y>>w;
- if (x == y)continue;
- v[x][1].push_back({y,w});
- v[y][1].push_back({x,w});
- }
- cin>>m;
- while (m--) {
- cin>>x>>y>>w;
- if (x == y)continue;
- v[x][2].push_back({y,w});
- v[y][2].push_back({x,w});
- }
- dijkstra(t , 1);
- dijkstra(t , 2);
- dfs(s , 1);
- if (f) {
- cout<<-1<<endl;
- exit(0);
- }
- memset(ans , -1 , sizeof(ans));
- ans[t][1] = ans[t][2] = 0;
- cout<<solve(s , 1)<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement