题解 SP50 【INCARDS - Invitation Cards】

· · 题解

原题

题目大意：给定一个简单有向图，设dis_{i,j}表示i到j的最短路径长度，求

\large \sum_{i=2}^n dis_{1,i} + \sum_{i=2}^n dis_{i,1}

思路

先跑一遍dijkstra，记录下dis数组的和

接着再对原图反向建边的图跑一边dijkstra，记录下dis数组的和

最后把两个和加起来就好了

小技巧：我们可以在输入边的时候建一条(v+n,u+n)的边作为反向边来存，但注意第二次dijkstra要将第n+1个点作为起点。

代码

const int N = 2e6 + 10;
int n,m,s = 1;
int cnt = 0;
int dis[N];
int vis[N];
int head[N];
struct edge
{
    int v,w;
    int nxt;
}edge[N];
struct node
{
    int dis,num;
    bool operator < (const node &x) const
        {return x.dis < dis;}
};
void add(int u , int v , int w)
{
    ++cnt;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
    return ;
}
void dijkstra()
{
    memset( dis , 127 , sizeof(dis) ); 
    memset( vis , false , sizeof(vis) ); 
    dis[s] = 0;
    pr_q<node> q;
    q.push( (node){0 , s} );
    while( !q.empty() )
    {
        int u = q.top().num;
        q.pop();
        if( vis[u] )
            continue;
        vis[u] = true;
        for(int i = head[u];i;i = edge[i].nxt)
        {
            int v = edge[i].v;
            if(dis[v] > dis[u] + edge[i].w)
            {
                dis[v] = dis[u] + edge[i].w;
                q.push( (node){dis[v] , v} );
            }
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset( head , 0 , sizeof(head) );
        cnt = 0;
        cin >> n >> m;
        int u,v,w;
        for(int i = 1;i <= m;i++)
        {
            cin >> u >> v >> w;
            add(u , v , w);
            add(v + n , u + n , w);
        }
        int ans = 0;
        s = 1;
        dijkstra();
        for(int i = 1;i <= n;i++)
            ans += dis[i];
        s = n + 1;
        dijkstra();
        for(int i = n + 1;i <= n * 2;i++)
            ans += dis[i];
        cout << ans << endl;
    }
    return 0;
}

PS:五倍经验

https://www.luogu.com.cn/problem/UVA721

https://www.luogu.com.cn/problem/P1342

https://www.luogu.com.cn/problem/P1629

https://www.luogu.com.cn/problem/P1821