洛谷 P1629 邮递员送信

这个里面判断的东西比较多

实际上不需要这么多的，数据给的很水

完全可以加上重边自环什么的

而且这道题完全暴力做n次dij（3*10^7比较危险）

比较优化的方法是：

第一遍dij算出邮递员到每个地方的距离

第二遍反向建边，横容易看出邮递员到每个地方的距离都是每个地方到邮递员的距离

这种方法就可以把单终点最短路径转变成单源最短路径

另外说明一下，因为跑两遍Dij，为了便于区分分开写的，变量名最后是1的是第一次dij有关，为2 则是第二次dij

上代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

int n,m;
int h1[1926],h2[1926];   
int s1,s2;
struct edge{
    int next,to,dis;
};
int v1[1926],v2[1926];
int d1[1926],d2[1926];
edge e1[200860],e2[200860];
int looker1[1020][1020];   //looker是得到i,j边距离最小值 
int looker2[1020][1020];
int l1[1020][1020];   //l1是标记i,j是否走过 
int l2[1020][1020];

void addedge1(int next,int to,int dis)
{
    e1[++s1].dis=dis;
    e1[s1].next=h1[next];
    e1[s1].to=to;
    h1[next]=s1;
}

void addedge2(int next,int to,int dis)
{
    e2[++s2].dis=dis;
    e2[s2].to=to;
    e2[s2].next=h2[next];
    h2[next]=s2;
}

void dij1(int start)
{
    priority_queue <pair<int,int> > q;   //pair的用法 
    memset(d1,0x3f,sizeof(d1));
    memset(v1,0,sizeof(v1));
    q.push(make_pair(0,start));
    d1[1]=0;
    while(!q.empty())
    {
        int i,j,k;
        int t=q.top().second;
        q.pop();
        if(v1[t]) continue;
        v1[t]=1;  
        for(i=h1[t];i;i=e1[i].next)
        {
            j=e1[i].to;
            if(l1[t][j]) continue;  //l1是判断t和j边是否走过一次，如果走过了还能走由Dij性质得到有重边 
            l1[t][j]=1;
            k=looker1[t][j];
            if(d1[t]+k<d1[j])
            {
                d1[j]=d1[t]+k;
                q.push(make_pair(-d1[j],j));
                 //pair第一个数据是由小到大的，因此需要取相反数
                //例如 5大于3，因此5先出队，但是取相反数之后-3就大与5了 
            }
        }
    }
}

void dij2(int start)
{    
    priority_queue <pair<int,int> > q; 
    memset(d2,0x3f,sizeof(d2));  //因为求最小值所以初值赋为极大值 
    memset(v2,0,sizeof(v2));
    q.push(make_pair(0,start));
    d2[1]=0;
    while(!q.empty())
    {
        int i,j,k;
        int t=q.top().second;
        q.pop();
        if(v2[t]) continue;
        
        v2[t]=1;
        for(i=h2[t];i;i=e2[i].next)
        {
            j=e2[i].to;
            k=looker2[t][j];
            if(l2[t][j]) continue;
            l2[t][j]=1;
            if(d2[t]+k<d2[j])
            {
                d2[j]=d2[t]+k;
                q.push(make_pair(-d2[j],j));
            }
        }
    }
}

int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    memset(looker1,0x3f,sizeof(looker1));
    memset(looker2,0x3f,sizeof(looker2));
    for(i=1;i<=m;i++)
    {
        int t1,t2,t3;
        scanf("%d %d %d",&t1,&t2,&t3);
        looker1[t1][t2]=min(looker1[t1][t2],t3);  //得到 t1,t2的最小值 
        looker2[t2][t1]=min(looker2[t2][t1],t3);
        addedge1(t1,t2,t3);
        addedge2(t2,t1,t3);  //反向建图 
    }
    int tot=0;
    dij1(1);
    dij2(1);
    for(i=1;i<=n;i++)
    {
        tot+=d1[i]+d2[i];
    }
    printf("%d",tot);
    return 0;
}