数据很水
  • 板块P3905 道路重建
  • 楼主ZhaoV1
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/6/24 19:47
  • 上次更新2024/6/24 22:43:22
查看原帖
数据很水
1212232
ZhaoV1楼主2024/6/24 19:47

虽然我很菜,但数据是真的水。

代码放在了最后,随便测一组样例:

6 9
1 2 10
2 4 20
2 6 30
1 6 40
1 3 50
3 4 70
3 5 80
5 6 90
1 5 60
3
1 2
1 6
1 3
1 4
输出答案应当是0,而本帖错误代码却是10

很好理解,本贴错误代码写出来压根不是为了求两点间最短修复道路,而是错误地求两点间最短道路之间要修复的道路长度,两者性质完全不同却判了正确。

错误但AC了本题的代码

#include <bits/stdc++.h>//配合P3371食用
#define int long long
using namespace std;
#define INF 0x3f3f3f3f
const int N = 1e2+5;
int t,n,m,d;
struct edge{
	int v,w;
};
map<pair<int,int>,int> mp;//哪条路被毁了
// dis[i]代表s点到i点的距离(暂时)
int dis[N],vis[N];
int road[N];//装路径的数组(表示从'pos1'到'i'的完整路径)
vector<edge> e[N];
// 堆优化dijkstra时间复杂度为O(m*logn)
struct inner_queue{
	int dis,id;
	bool operator < (const inner_queue &b) const{
		return this->dis > b.dis;
	}
};
priority_queue<inner_queue> que;

void dijkstra(int s){
	for(int i=1;i<=n;i++) dis[i] = INF, vis[i] = 0;
	dis[s] = 0;
	que.push({dis[s],s});

	while(!que.empty()){
		auto temp = que.top();
		que.pop();

		if(vis[temp.id]) continue;
		vis[temp.id] = 1;

		for(auto i : e[temp.id]){
			if(dis[i.v] > dis[temp.id] + i.w){
				road[i.v] = road[temp.id];
				if(mp[{temp.id,i.v}] || mp[{i.v,temp.id}]) road[i.v] += i.w; 
				dis[i.v] = dis[temp.id] + i.w;
				que.push({dis[i.v],i.v});
			}
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i=1,pos1,pos2,temp;i<=m;i++){
		cin >> pos1 >> pos2 >> temp;
		e[pos1].push_back({pos2,temp});//有向边
		e[pos2].push_back({pos1,temp});
	}
	cin >> d;
	for(int i=1,pos1,pos2;i<=d;i++){
		cin >> pos1 >> pos2;
		mp[{pos1,pos2}] = 1;//被毁掉的路
	}
	int pos1,pos2;
	cin >> pos1 >> pos2;
	dijkstra(pos1);
	cout << road[pos2] << '\n';
}


signed main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	t = 1;
	while(t--){
		solve();
	}
	return 0;
}
2024/6/24 19:47
加载中...