Submission #8060283


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

template<class T>
struct Edge{
	int from,to;
	T cost;
	Edge(int to,T cost) : to(to),cost(cost){}
	Edge(int from,int to,T cost) : from(from),to(to),cost(cost){}
};

template<class T>
using WeightedGraph = vector<vector<Edge<T>>>;
using Graph = vector<vector<int>>;
template<class T>
using Matrix = vector<vector<T>>;

template<class T>
void warshallFloyd(Matrix<T> &G){
	for(int k = 0;k < G.size();k++){
		for(int i = 0;i < G.size();i++){
			for(int j = 0;j < G.size();j++){
				if(G[i][k] == INF || G[k][j] == INF) continue;
				G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
			}
		}
	}
}

signed main(){
	int n,m,l;
	cin >> n >> m >> l;
	Matrix<int> G(n,vector<int>(n,INF)),G2 = G;
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c; a--;b--;
		chmin(G[a][b],c);
		chmin(G[b][a],c);
	}
	warshallFloyd(G);
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			if(G[i][j] <= l){
				chmin(G2[i][j],1ll);
				chmin(G2[j][i],1ll);
			}
		}
	}
	warshallFloyd(G2);
	int q;
	cin >> q;
	for(int i = 0;i < q;i++){
		int s,t;
		cin >> s >> t; s--;t--;
		if(G2[s][t] != INF) cout << G2[s][t] - 1 << endl;
		else cout << -1 << endl;
	}
}

Submission Info

Submission Time
Task E - Travel by Car
User hoget157
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2032 Byte
Status AC
Exec Time 290 ms
Memory 1920 KB

Judge Result

Set Name Sample All after_contest (0)
Score / Max Score 0 / 0 500 / 500 0 / 0
Status
AC × 3
AC × 50
AC × 1
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49
after_contest (0) after_contest_00
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 219 ms 1920 KB
01-handmade-04 AC 290 ms 1792 KB
01-handmade-05 AC 288 ms 1792 KB
01-handmade-06 AC 233 ms 1920 KB
01-handmade-07 AC 238 ms 1920 KB
02-random-08 AC 4 ms 256 KB
02-random-09 AC 17 ms 384 KB
02-random-10 AC 225 ms 1920 KB
02-random-11 AC 11 ms 384 KB
02-random-12 AC 27 ms 512 KB
02-random-13 AC 34 ms 512 KB
02-random-14 AC 201 ms 1408 KB
02-random-15 AC 221 ms 1920 KB
02-random-16 AC 89 ms 896 KB
02-random-17 AC 145 ms 1280 KB
02-random-18 AC 12 ms 384 KB
02-random-19 AC 2 ms 256 KB
02-random-20 AC 221 ms 1920 KB
02-random-21 AC 49 ms 640 KB
02-random-22 AC 1 ms 256 KB
02-random-23 AC 82 ms 768 KB
02-random-24 AC 235 ms 1536 KB
02-random-25 AC 222 ms 1920 KB
02-random-26 AC 3 ms 256 KB
02-random-27 AC 104 ms 1024 KB
02-random-28 AC 124 ms 1024 KB
02-random-29 AC 107 ms 896 KB
02-random-30 AC 226 ms 1920 KB
02-random-31 AC 12 ms 384 KB
02-random-32 AC 79 ms 896 KB
02-random-33 AC 101 ms 896 KB
02-random-34 AC 80 ms 768 KB
02-random-35 AC 223 ms 1920 KB
02-random-36 AC 67 ms 768 KB
02-random-37 AC 94 ms 896 KB
02-random-38 AC 1 ms 256 KB
02-random-39 AC 5 ms 256 KB
02-random-40 AC 225 ms 1920 KB
02-random-41 AC 232 ms 1792 KB
02-random-42 AC 38 ms 512 KB
02-random-43 AC 219 ms 1536 KB
02-random-44 AC 2 ms 256 KB
02-random-45 AC 220 ms 1920 KB
02-random-46 AC 16 ms 384 KB
02-random-47 AC 167 ms 1408 KB
02-random-48 AC 1 ms 256 KB
02-random-49 AC 24 ms 384 KB
after_contest_00 AC 279 ms 1792 KB