只过了最后一个点

P1342 请柬

桑梓暖阳 @ 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,我也在这儿错了


|