Submission #777297

#	Time	Username	Problem	Language	Result	Execution time	Memory
777297		Alora	Robot (JOI21_ho_t4)	C++17	0 / 100	3086 ms	24916 KiB

Main

#include <bits/stdc++.h>
#define name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int n, m;
struct dl{
    ll h;
    int a, b, c;
    bool operator < (const dl &o) const {return h > o.h;}
};
vector <dl> g[maxn];

ll cost[1003][2003], dp[1003][2003];
void sub1(){
    fi(i, 1, n)
        fi(j, 0, m) dp[i][j] = 1e18;
    priority_queue <dl> q;
    dp[1][0] = 0;
    q.push({0, 1, 0, 0});
    while(q.size()){
        auto [h, u, x, y] = q.top(); q.pop();
        if(h != dp[u][x]) continue;
        fi(i, 1, m){
            for(auto [v, cl, p, id]: g[u]){
                int tmp = 0;
                if(cl == x) tmp = y;
                if(dp[v][cl] > h + cost[u][cl] - p + tmp){
                    dp[v][cl] = h + cost[u][cl] - p + tmp;
                    q.push({dp[v][cl], v, cl, p});
                }
                if(dp[v][0] > h + p){
                    dp[v][0] = h + p;
                    q.push({dp[v][0], v, 0, p});
                }
            }
        }
    }
    ll res = 1e18;
    fi(i, 0, m) res = min(res, dp[n][i]);
    if(res != 1e18) cout << res;
    else cout << -1;
    exit(0);
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
  //  freopen(name".in", "r", stdin);
 //   freopen(name".out", "w", stdout);
    cin >> n >> m;
    fi(i, 1, m){
        int u, v, c, p; cin >> u >> v >> c >> p;
        g[u].pb({v, c, p, i});
        g[v].pb({u, c, p, i});
        cost[u][c] += p;
        cost[v][c] += p;
    }
    if(n <= 1000 && m <= 2000) sub1();
}

Compilation message (stderr)

Main.cpp: In function 'void sub1()':
Main.cpp:39:40: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   39 |                     q.push({dp[v][cl], v, cl, p});
      |                                        ^
Main.cpp:43:39: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   43 |                     q.push({dp[v][0], v, 0, p});
      |                                       ^

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42