代码里用了 map 数组来对边进行去重
可以帮忙看一下我的代码有什么问题吗?
#include <bits/stdc++.h>
using namespace std;
#define infinity 2147483647
#define space 100002
struct point{
int nextnum;
vector <int> nextpoint,nextweigh;
int shortest_weigh=infinity;
};
struct edge{
int a,b,c;
}edges[space*5];
int n,m,s;
int u,v,w;
queue <int> nextpoints;
point graph[space];
void init(edge z){
graph[z.a].nextnum++;
graph[z.a].nextpoint.push_back(z.b);
graph[z.a].nextweigh.push_back(z.c);
}
map <pair <int,int> , int> costs;
bool equal(edge x,edge y){
return x.a==y.a&&x.b==y.b;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
cin>>edges[i].a>>edges[i].b>>edges[i].c;
pair <int,int> x=make_pair(edges[i].a,edges[i].b);
if(costs.find(x)==costs.end())costs[x]=edges[i].c;
else costs[x]=min(edges[i].c,costs[x]);
}
for(map <pair <int,int> , int> :: iterator iter=costs.begin();iter!=costs.end();iter++){
graph[iter->first.first].nextpoint.push_back(iter->first.second);
graph[iter->first.first].nextweigh.push_back(iter->second);
graph[iter->first.first].nextnum++;
}
// for(int i=1;i<=m;i++){
// cin>>u>>v>>w;
// graph[u].nextpoint.push_back(v);
// graph[u].nextweigh.push_back(w);
// graph[u].nextnum++;
// }
//声明:本题只限于边权>0的简单图。
nextpoints.push(s);
graph[s].shortest_weigh=0;
while(nextpoints.size()){
int top=nextpoints.front();
nextpoints.pop();
for(int i=0;i<graph[top].nextnum;i++){
if(graph[top].shortest_weigh+graph[top].nextweigh[i]<graph[graph[top].nextpoint[i]].shortest_weigh)
graph[graph[top].nextpoint[i]].shortest_weigh=graph[top].shortest_weigh+graph[top].nextweigh[i],nextpoints.push(i);
}
for(int i=1;i<=n;i++){
cout<<graph[i].shortest_weigh<<" ";
}
}
for(int i=1;i<=n;i++){
cout<<graph[i].shortest_weigh<<" ";
}
return 0;
}