虽然我很菜,但数据是真的水。
代码放在了最后,随便测一组样例:
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
很好理解,本贴错误代码写出来压根不是为了求两点间最短修复道路,而是错误地求两点间最短道路之间要修复的道路长度,两者性质完全不同却判了正确。
#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;
}