洛谷 P1685 游览 题解+tip【拓扑排序】【组合数学】

点击量：131

   有向图拓扑排序+加法/乘法原理。

目录

题目描述

顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！

 

你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。

 

我们把桃花岛抽象成了一个图，共n个点代表路的相交处，m条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。

 

你的任务是：把所有不同的路线游览完一共要花多少时间？

 

输入输出格式

输入格式：

第1行为5个整数：n、m、s、t、t0，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从1到n）和你乘船从岛东头到西头一次的时间。

 

以下m行，每行3个整数：x、y、t，表示从点x到点y有一条行走耗时为t的路。

 

每一行的多个数据之间用一个空格隔开，且：2<=n<=10000; 1<=m<=50000;t<=10000;t0<=10000

 

输出格式：

假设总耗时为total,则输出total mod 10000的值（total对10000取余）。

 

输入输出样例

输入样例#1：

3 4 1 3 7

1 2 5

2 3 7

2 3 10

1 3 15

输出样例#1：

56

说明

【样例说明】

共有3条路径可以从点1到点3，分别是1-2-3,1-2-3,1-3。

 

时间计算为：(5+7)+7+(5+10)+7+(15)=56

题解：

   对于每个点，能到达它的方案一定是能到达指向它的点的方案之和，也就是加法原理。而每次不同路线会经过相同的边，统计前面的方案数，乘上边权，再继承（加上）所来点的总时间，就是到达它的总时间。因为每个点总是用到了它前面点的状态，且图没有重边，自环不用加边，就会想拓扑排序。

   对于各个点来说，从它的所有入边都能引出方案数和时间总数，时间总数在通过(u,v)路径转移时要乘上u的方案数。因为此时u已经可以转移了，说明u的拓扑序已经排到了，而v的拓扑序还没有排到，根据逻辑关系，我们要乘的是u的方案数，去转移v的方案数，有点像DP里面的刷表法。

总结：

   这几天老是被long long坑，对于这些要模的题或者其他答案较大的题，很有可能int相乘乘爆。例如

(long long)c=(int)a*(int)b

   当a*b超过int所能表示的整数范围时，它仍然返回int范围内的值，尽管左边是long long，但还是赋值为int。

(int)c=(int)a*(int)b%(int)质数

   在这种情况下因为*和%优先级相等，所以从左向右计算。当这个质数超过100000左右，或者说a,b本身较大，就会先计算a,b，也就可能乘爆。因此，我们要么在这个题地代码里尽可能多地定义long long，要么就在可能爆炸的地方打上括号（括号也很玄学，最好每两个运算符之间都打括号）。

Code：

#include<cstdio>
#include<cstring>
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[51000];
int head[10100],cnt=-1;
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
}
int s,t;
int q[123456],l=0,r=0;
int in[10100];
long long way[10100],tm[10100];//方案数和总用时
void bfs()
{
    in[s]=0;
    way[s]=1;
    q[++r]=s;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
        {
            way[e[i].n]+=way[k]%10000;
            tm[e[i].n]+=(tm[k]+way[k]*e[i].v%10000)%10000;记得加上tm[k]
            in[e[i].n]--;
            if(!in[e[i].n])
                q[++r]=e[i].n;
        }
    }
}
int main()
{
    int n,m,t0,u,v,w;
    scanf("%d%d%d%d%d",&n,&m,&s,&t,&t0);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        if(u==v)
            continue;
        add(u,v,w);
        in[v]++;
    }
    bfs();
    printf("%d\n",((way[t]-1)*t0+tm[t]+10000)%10000);
    return 0;
}