CSU-ACM2017暑期训练14-最短路 D - 输入量很大的模板题

D - 输入量很大的模板题

In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery.

The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where 'X' denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.

All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.

Input

 The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.

Output

For each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.

Sample Input

Sample Output

4
210

这题做了3小时，想砍人的冲动都有喽。原来是因为看错了题目，搞错了答案的数字范围。最坑爹的是，这次的题目是POJ上的，而我查题解查出来的是HDU的题解。百般无奈的下我拷了标程直接提交，竟然也是错的。这下我彻底怀疑人生了，甚至思考是不是POJ真的开始给Vjudge随机出结果。而当我最终知晓此题为POJ之题，再看了一下标程，才猛然觉悟，检查是不是 sum 的范围给弄小了，顺手改了个long long，一交，过了……感觉自己做了一道送命题。

现在来分析一下这题。
这题本不难的，能做3小时，跟我还未掌握SPFA这个算法和邻接表的建立方法也有关系，为理解此算法大约花去1小时。为了今后对SPFA印象深刻，决定将解析写得丰富一些，同时纪念这道题目。

邻接表就不说了，看【坐在马桶上看算法】巧妙的邻接表这个文章即可完全理解。
至于SPFA，实际上跟广度优先搜索有点像。事先假定起点与所有点之间的距离都是无穷大，并且准备一个队列，将起点压入队列。我们弹出队首元素，查看它临近它的点与它的间距，若小于先前认为的“最短长度”，则更新这个间距，同时将这个临近点压入队列，否则不执行队列操作，如此往复，直到队列为空。这样一来，我们就得到了起点与任何一个可以到达的点之间的最短距离。SPFA的例子可以参考SPFA 算法详解( 强大图解，不会都难！) 这篇博客，其中的图例思路十分清晰，一目了然。

题目要求给出临时工从总站出发到达各个公交站以及从各个公交站返回总站所需的最少花费，而花费和路程成正比，也就是说我们需要求出1号公交站到所有公交站最短距离之和，以及各个公交站返回1号公交站的最短距离之和。一开始可能会想只求1号站到各个站的距离之和乘二，但是要注意到题目中所给皆为单向边，故不可简单乘二。但若一个一个地枚举，计算量又太大，耗时是无法想象的。
其实这题采用直译法即可得解，既然题目要求算出两个方向的最短距离，我们就计算两次SPFA。不过计算之前需要预处理邻接表。方法十分简单，即将邻接表中的起点与终点互换。在初次掌握邻接表的情况下，可能造成错误的地方应该就在于将邻接表反向时的细节了。一定要注意 Next[] 数组和 first[] 数组的重新计算。
一旦完成了邻接表的反向，即可再次执行SPFA运算过程。将两次得到的距离数组 d[] 中元素之和输出即得答案。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e6+19, INF = 0x3f3f3f3f;

struct node{
int u, v, w;
}e[maxn];

int first[maxn], Next[maxn], v[maxn], w[maxn], d[maxn];
int cnt, n, m;// n 是站点数， m 是路线数.

void spfa(int src){
queue<int> Q;
    d[src] = 0;
    Q.push(src);
while(!Q.empty()){
int u = Q.front();
        Q.pop();
for(int i = first[u]; i != -1; i = Next[i]){
if(d[v[i]] > d[u] + w[i]){
                d[v[i]] = d[u] + w[i];
                Q.push(v[i]);
            }
        }
    }
}

void makeEdge(int a, int b, int c){
    v[cnt] = b;
    w[cnt] = c;
    Next[cnt] = first[a];
    first[a] = cnt;
    cnt++;
}

void init(){
memset(Next, -1, sizeof(Next));
memset(first, -1, sizeof(first));
for(int i = 0; i <= n; i++)
        d[i] = INF;
    cnt = 0;
}

int main(){
#ifdef TEST
freopen("test.txt", "r", stdin);
#endif // TEST

int T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
        init();
for(int i = 0; i < m; i++){
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
            makeEdge(e[i].u, e[i].v, e[i].w);
        }
long long sum = 0;
        spfa(1);
for(int i = 2; i <= n; i++)
            sum += d[i];
        init();
for(int i = 0; i < m; i++)
            makeEdge(e[i].v, e[i].u, e[i].w);
        spfa(1);
for(int i = 2; i <= n; i++)
            sum += d[i];
printf("%lld\n", sum);
    }

return 0;
}

秒客网

CSU-ACM2017暑期训练14-最短路 D - 输入量很大的模板题

D - 输入量很大的模板题

相关文章