不知怎么改了
  • 板块学术版
  • 楼主chrisxu1
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/16 20:12
  • 上次更新2024/12/16 23:46:54
查看原帖
不知怎么改了
776355
chrisxu1楼主2024/12/16 20:12

题目:P5683 [CSP-J2019 江西] 道路拆除

#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<map>
#include<deque>
#include<stack>
#include<set>
#include<vector>
#define ll long long
#define ull unsigned long long
using namespace std;
typedef pair<ll, ll> PII;
ll vis[100005], dis[100005];
ll n, m, cnt, c[10005][10005];
ll x[3005], y[3005];
ll s1, s2, t1, t2;
vector<pair<ll, ll> > edge[100005];
void dijkstra(ll st){
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	dis[st] = 0;
	priority_queue<PII, vector<PII>, greater<PII> > q;
	q.push(make_pair(0, st));
	while(!q.empty()){
		ll d = q.top().first;
		ll v = q.top().second;
		q.pop();
		if(vis[v]) continue;
		vis[v] = 1;
		for(auto it : edge[v]){
			ll to = it.first;
			ll w = it.second;
			if(dis[v] + w < dis[to]){
				dis[to] = dis[v] + w;
				q.push(make_pair(dis[to], to));
			}
		}
	}
}
int main(){
	//freopen("fraction.in","r",stdin);
	//freopen("fraction.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= m; i ++){
		cin >> x[i] >> y[i];
		edge[x[i]].push_back(make_pair(y[i], 1));
		edge[y[i]].push_back(make_pair(x[i], 1));
	}
	cin >> s1 >> t1 >> s2 >> t2;
	dijkstra(1);
	if(dis[s1] > t1 || dis[s2] > t2){
		cout << -1;
		return 0;
	}
	for(int i = 1; i <= m; i ++){
		edge[x[i]][++ c[x[i]][y[i]]] = make_pair(0, 0);
		edge[y[i]][++ c[y[i]][x[i]]] = make_pair(0, 0);
		dijkstra(1);
//		cout << endl << endl;
//		for(int i = 1; i <= n; i ++){
//			cout << dis[i] << " ";
//		}
//		cout << endl << endl;
		if(dis[s1] > t1 || dis[s2] > t2){
			edge[x[i]].push_back(make_pair(y[i], 1));
			edge[y[i]].push_back(make_pair(x[i], 1));
		} else {
			cnt ++;
			cout << x[i] << " " << y[i] << endl;
		}
	}
	cout << cnt;
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

帮忙调代码,蒟蒻知道哪里错了,可不知怎么调,望评

2024/12/16 20:12
加载中...