Submission #65966

#	Time	Username	Problem	Language	Result	Execution time	Memory
65966		ikura355	007 (CEOI14_007)	C++14	0 / 100	5 ms	1104 KiB

007

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e3 + 5;
const int inf = 1e9;

struct node {
	int u,val;
	node(int _u = 0, int _val = 0) {
		u = _u; val = _val;
	}
	bool operator < (node a) const {
		return a.val<val;
	}
};

int n,m,a,b,s1,s2;
vector<int> way[maxn];
int len[maxn];
priority_queue<node> heap;
int d1[maxn], d2[maxn];

int sssp(int u) {
	for(int i=1;i<=n;i++) len[i] = inf;
	len[u] = 0;
	heap.push(node(u,0));
	while(!heap.empty()) {
		auto t = heap.top(); heap.pop();
		int u = t.u, val = t.val;
		if(len[u]!=val) continue;
		for(auto v : way[u]) {
			if(len[v] > len[u] + 1) {
				len[v] = len[u] + 1;
				heap.push(node(v,len[v]));
			}
		}
	}
}

//bool check(int val) {
//    sssp(a,val);
//    for(int i=1;i<=n;i++) d1[i] = len[i];
//    sssp(b,0,a);
//    for(int i=1;i<=n;i++) d2[i] = len[i];
//    if(d2[s1]<d1[s1] || d2[s2]<d1[s2]) return 0;
//    return 1;
//}

int main() {
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&a,&b,&s1,&s2);
	for(int i=1;i<=m;i++) {
		int u,v; scanf("%d%d",&u,&v);
		way[u].push_back(v); way[v].push_back(u);
	}
	sssp(a);
	for(int i=1;i<=n;i++) d1[i] = len[i];
	sssp(b);
	for(int i=1;i<=n;i++) d2[i] = len[i];
	if(d2[s1]<d1[s1] || d2[s2]<d1[s2]) printf("-1");
	else {
        int res = min(d2[s1]-d1[s1], d2[s2]-d1[s2]);
        if(res==0) printf("0");
        else if((d1[s1]>d1[s2])!=(d2[s1]>d2[s2])) printf("%d",res);
        else assert(0);
	}
}

Compilation message (stderr)

007.cpp: In function 'int sssp(int)':
007.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
007.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&a,&b,&s1,&s2);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70