一、题目大意

给出一张图\(G\)，\(G\)中有\(n\)个带权值的点，点\(i\)的权值为\(t[i]\)，点与点之间有\(m\)条连边，求从点\(1\)到点\(n\)之间的最短路长度并计算数目。
其中\(1 \leq n,m \leq 100000\)，\(1 \leq t[i] \leq 10000\)。

二、算法分析

本题是最短路计数模板题的变形，从边权值变形为点权值，但是实际实现时并无本质区别，因此可以采用狄杰斯特拉算法来解决。在实现过程中，对于点权值问题，我们从将要扩展的点的集合中取出一个点\(u\)进行扩展，此时对未进行扩展的点\(v\)，若\(u\)与\(v\)之间存在连边，则可以将后向点\(v\)的权值视作这条边的权值，如此处理就可以使用狄杰斯特拉算法进行计算。

算法正确性说明：在处理每条边时的顺序类似拓扑排序，每条边都被处理一次，因此可以用后向点权值代替整条边的权值。

三、代码实现

首先考虑图的存储问题。为了节省空间，采用链式前向星存储图的方式，定义edge结构体用来存储边的终点to和后继next，head数组中head[u]存储以u为起点的边，并定义addedge函数用来收集信息。（其中cnt和head数组的初始值均为\(-1\)） 

struct edge {
    int to;
    int next;
} e[M * 2];//存边
int head[N];//邻接表存边
int cnt = -1;
void addedge(int u, int v) {
    e[++cnt].next = head[u],head[u] = cnt,e[cnt].to = v;
}//加边

考虑本题数据范围，朴素的狄杰斯特拉算法的时间复杂度为\(O(n^2)\)，会导致超时，因此考虑使用优先队列进行优化。由于本课程OJ禁止使用STL标准库，因此考虑手动实现优先队列。优先队列中需要存储点的信息——点的编号和当前点到初始结点1的距离最小值，因此首先定义结构体point用来存储点，同时在结构体中重载>和<运算符，以方便维护队列顶的最大优先级元素信息。
之后我们可以定义优先队列PriorityQueue类。类中private元素为用于存储点的point类型数组*p以及队列长度len，定义构造函数如下用于初始化。 

PriorityQueue(int n) {
    p = new point[n + 1];
    len = 0;
    }//优先队列的构造函数

优先队列支持插入元素维护有序性，以及获取顶端元素并弹出。这些操作的核心在于“上浮”函数up和“下沉”函数down。优先队列本质是建立了一颗完全二叉树，向上更新结点时，将儿子与父亲比较，不断将优先级更大的结点上浮。下沉时则反向一层层比较，维护优先队列的有序性。具体实现如下： 

void up(int k) {
    while(k > 1 && p[k] > p[k / 2]) {
        swap(p[k / 2], p[k]);
        k /= 2;
    }
}//向上更新结点，将儿子与父亲比较，不断将优先级更大的结点上浮

void down(int k) {
    while(2 * k <= len) {
        int j = 2 * k;
        if(j < len && (p[j] < p[j + 1])) j ++;
        if(p[k] > p[j]) break;
        swap(p[k], p[j]);
        k = j;
    }
}//向下维护顺序，维护优先队列的有序性

借助“上浮”和“下沉”操作，便可以进行insert插入和delmax获取顶端元素并弹出。插入时，在数组末尾加入新元素，并从尾部开始上浮维护即可。弹出时，首先获取最大优先级元素p[1]，之后将p[1]与p[len]交换位置，将长度减\(1\)后从顶端开始下沉维护，最后返回获取的p[1]即可。 

point delmax() {
    point max = p[1];
    swap(p[1], p[len--]);
    down(1);
    return max;
}//获取当前优先级最大的元素，并且弹出该元素

void insert(point v) {
    p[++len] = v;
    up(len);
}//插入元素v

同时，为了方便实现，还需定义函数is_empty用来判断优先队列是否为空，直接返回len == 0的值即可。

实现了优先队列之后，我们就可以编写优化的狄杰斯特拉算法。首先定义优先队列pq，定义数组dis和sum分别用来存储最短路径长度和最短路径数目，定义数组pweight用来存储每个点的权值。算法开始时先将dis数组初始化为一个上界值inf=0x3f3f3f3f，之后令dis[1] = pweight[1]，sum[1] = 1作为结点1的初始值，进入优先队列。定义数组visited表示结点是否已被扩展，此后当优先队列不为空时，进行贪心更新操作：获取当前队列顶端点p，遍历与p相连的终点q，若dis[q] > dis[p] + pweight[q]，则更新dis[q]为dis[p] + pweight[q]，同时更新sum[q]为sum[p]，并将更新后的结点q入队。若上述两值相等，则更新sum[q] = sum[q] + sum[p]，注意题目要求取模即可。这样就实现了优化的狄杰斯特拉算法。核心代码如下： 

while(!pq.is_empty()) {
    point temp = pq.delmax();
    int p = temp.num;
    if(visited[p]) continue;
    visited[p] = 1;
    for(int i = head[p]; ~i; i = e[i].next) {
        int q = e[i].to;
        if(dis[q] > dis[p] + pweight[q]) {
            dis[q] = dis[p] + pweight[q];
            sum[q] = sum[p];
            pq.insert(point{q, dis[q]});
        }
        else if(dis[q] == dis[p] + pweight[q]) sum[q] = (sum[p] + sum[q]) % mod;
    }    
}

最终主函数中，读取输入后存储边信息，调用狄杰斯特拉算法即可。

四、实现中值得注意的细节

  1. 本题中边为双向边，因此在读取输入加边时，要同时进行addedge(u, v)和addedge(v, u)操作，保存边信息的数组大小为m * 2，否则会导致Wrong Answer。

  2. 由于运算过程中dis和sum数组中的结果可能过大，因此采用long long数据类型进行存储。

五、时间与空间复杂度分析

  1. 本题中，朴素狄杰斯特拉算法的时间复杂度为\(O(n^2)\)，优化后的狄杰斯特拉算法时间复杂度为\(O(m\log{n})\)。

  2. 本题中，用于存储边信息的空间为\(O(m)\)，存储点信息的优先队列的空间为\(O(n)\)，则整体的空间复杂度为\(O(m+n)\)。