oj.uz

Submission #224105

# Submission time Handle Problem Language Result Execution time Memory
224105 2020-04-17T08:08:48 Z oolimry Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 103 ms 4456 KB 
#include <bits/stdc++.h>

using namespace std;
long long inf = (1LL << 56LL);

typedef pair<long long, long long> ii;
vector<ii> adj[205];
vector<ii> adjR[205];
long long dis[205];
long long dis1[205];
long long disn[205];
long long dis1R[205];
long long disnR[205];

int n, m; 

long long dij(int s, int t){
	fill(dis, dis + (n+3), inf);
	
	priority_queue<ii, vector<ii>, greater<ii> > dtr; /// use greater<int>
	dtr.push(ii(0,s));
    dis[s] = 0;
    ///first is minpath, second is vertex
    while(!dtr.empty()){
        ii cur = dtr.top();
        dtr.pop();
        for(int j = 0;j < adj[cur.second].size();j++){
            ii nei = adj[cur.second][j];
            if(nei.first + cur.first < dis[nei.second]){
                dis[nei.second] = nei.first + cur.first;
                dtr.push(ii(dis[nei.second],nei.second));
            }
        }
    }
    return dis[t];
}
/*
long long dijR(int s, int t){
	fill(dis, dis + (n+1), inf);
	
	priority_queue<ii, vector<ii>, greater<ii> > dtr; /// use greater<int>
	dtr.push(ii(0,s));
    dis[s] = 0;
    ///first is minpath, second is vertex
    while(!dtr.empty()){
        ii cur = dtr.top();
        dtr.pop();
        for(int j = 0;j < (int) adjR[cur.second].size();j++){
            ii nei = adjR[cur.second][j];
            if(nei.first + cur.first < dis[nei.second]){
                dis[nei.second] = nei.first + cur.first;
                dtr.push(ii(dis[nei.second],nei.second));
            }
        }
    }
    return dis[t];
}
*/
struct edge{
	long long u; long long v; long long c; long long d;
};
vector<edge> edges;

void prin(long long ans){
	if(ans >= inf) ans = -1;
	cout << ans;
	exit(0);
}

void subtask1(){
	long long ans = dij(1, n)+ dij(n, 1);
	for(int i = 0;i < m;i++){
		for(int i = 1;i <= n;i++) adj[i].clear();
		
		long long res = 0;
		for(int j = 0;j < m;j++){
			edge e = edges[j];
			if(i == j){
				adj[e.v].push_back(ii(e.c,e.u));
				res += e.d;
			}
			else adj[e.u].push_back(ii(e.c,e.v));
		}
		//cout << dij(1,n) + dij(n,1) + res << "\n";
		ans = min(ans, dij(1,n) + dij(n,1) + res);
	}
	
	prin(ans);
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		long long u, v, c, d; cin >> u >> v >> c >> d;
		edges.push_back({u,v,c,d});
		adj[u].push_back(ii(c,v));
		adjR[v].push_back(ii(c,u));
	}
	
	if(m <= 1000) subtask1();
	/*
	dij(1,n);
	for(int i = 1;i <= n;i++) dis1[i] = dis[i];
	
	dij(n,1);
	for(int i = 1;i <= n;i++) disn[i] = dis[i];
	
	dijR(1,n);
	for(int i = 1;i <= n;i++) dis1R[i] = dis[i];
	
	dijR(n,1);
	for(int i = 1;i <= n;i++) disnR[i] = dis[i];
	
	long long ans = dis1[n] + disn[1];
	for(edge e : edges){
		ans = min(ans, e.d + dis1[n] + disn[e.v] + dis1R[e.u] + e.c);
		ans = min(ans, e.d + disn[1] + dis1[e.v] + disnR[e.u] + e.c);
	}
	*/
	//prin(ans);
}

Compilation message

ho_t4.cpp: In function 'long long int dij(int, int)':
ho_t4.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < adj[cur.second].size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 73 ms 384 KB Output is correct
5 Correct 37 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 18 ms 512 KB Output is correct
10 Correct 103 ms 512 KB Output is correct
11 Correct 98 ms 512 KB Output is correct
12 Correct 100 ms 512 KB Output is correct
13 Correct 42 ms 512 KB Output is correct
14 Correct 53 ms 512 KB Output is correct
15 Correct 47 ms 512 KB Output is correct
16 Correct 59 ms 384 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 4456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 496 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Incorrect 22 ms 4212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 73 ms 384 KB Output is correct
5 Correct 37 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 18 ms 512 KB Output is correct
10 Correct 103 ms 512 KB Output is correct
11 Correct 98 ms 512 KB Output is correct
12 Correct 100 ms 512 KB Output is correct
13 Correct 42 ms 512 KB Output is correct
14 Correct 53 ms 512 KB Output is correct
15 Correct 47 ms 512 KB Output is correct
16 Correct 59 ms 384 KB Output is correct
17 Incorrect 30 ms 4456 KB Output isn't correct
18 Halted 0 ms 0 KB -