桑梓暖阳 @ 2016-10-03 17:53:55
各位神犇帮忙看一下吧,我的思路就是把图反向跑两遍最短路(dijkstra我复制了两遍使代码有点长)
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define MP(x,y) make_pair(x,y)
#define N 1000005
#define M 1000005
using namespace std;
int n,m,num,ans;
typedef pair<int,int> pii;
struct edge{int x,y,l,ne;} e1[M],e2[M];
int dis[N],v1[N],v2[N];
bool vis[N];
void add(int x,int y,int l){
e1[++num].x=x; e1[num].y=y; e1[num].l=l;
e1[num].ne=v1[x]; v1[x]=num;
e2[num].x=y; e2[num].y=x; e2[num].l=l;
e2[num].ne=v2[y]; v2[y]=num;
}
void dj(){
priority_queue<pii,vector<pii>,greater<pii> > que;
memset(dis,10,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[1]=0;
que.push(MP(0,1));
int x,y;
while(!que.empty()){
x=que.top().second; que.pop();
if(vis[x]) continue;
vis[x]=true;
for(int i=v1[x];i;i=e1[i].ne){
y=e1[i].y;
if(dis[y]>dis[x]+e1[i].l){
dis[y]=dis[x]+e1[i].l;
que.push(MP(dis[y],y));
}
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
}
void dj2(){
priority_queue<pii,vector<pii>,greater<pii> > que2;
memset(dis,10,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[1]=0;
que2.push(MP(0,1));
int x,y;
while(!que2.empty()){
x=que2.top().second; que2.pop();
if(vis[x]) continue;
vis[x]=true;
for(int i=v2[x];i;i=e2[i].ne){
y=e2[i].y;
if(dis[y]>dis[x]+e2[i].l){
dis[y]=dis[x]+e2[i].l;
que2.push(MP(dis[y],y));
}
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dj();
dj2();
printf("%d",ans);
return 0;
}
by Kwork @ 2016-10-03 19:44:12
瞄了一下,看到你memset(dis,10,sizeof(dis)),这明显是错的,其他的-------算法没有错。
by 桑梓暖阳 @ 2016-10-04 22:45:32
循环改成全赋成1000000000,依然不对啊
by 青丝、暮成雪 @ 2016-10-28 11:46:05
数据比较大,要用long long,我也在这儿错了