洛谷1608 路径统计

最短路计数模板。

注意这道题要去掉重边造成的影响。

对于每个点，记录一下从起点出发，到达这个点的最短路条数。

转移的时候，如果访问到了一个未访问的点，或者松弛操作成功，那就直接转移过去。

否则，如果遇到了一个访问过的点，那就看一下到这个点的距离是否等于当前点的距离+边权，是的话就说明从当前点走到这个点也是最短路，就直接加上即可。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <queue>
#include <functional>
#include <cstring>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 2000;
const int_t INF = 0x7fffffff;
struct Edge {
	int_t to;
	int_t weight;
	Edge(int_t to = -1 ,int_t weight = 0) {
		this -> to = to;
		this -> weight = weight;
	}
	bool operator<(const Edge& x) const {
		return to < x.to;
	}
	bool operator==(const Edge& x) const {
		return to == x.to;
	}
};

struct Pair {
	int_t dis;
	int_t vertex;
	Pair(int_t dis,int_t vertex) {
		this -> dis = dis;
		this -> vertex = vertex;
	}
	bool operator>(const Pair& pair) const {
		return dis > pair.dis;
	}

};

std::vector<Edge> graph[LARGE + 1];

void pushEdge(int_t from,int_t to,int_t weight) {
	graph[from].push_back(Edge(to,weight));
//    graph[to].push_back(Edge(from,weight));
}
bool visited[LARGE + 1];
int_t dis[LARGE + 1];
int_t count[LARGE + 1];
int_t n,m;
void Dijkstra() {
	std::fill(dis + 1 ,dis + 1 + n,INF);
	count[1] = 1;
	dis[1] = 0;
	std::priority_queue<Pair,std::vector<Pair>,std::greater<Pair> > heap;
	heap.push(Pair(0,1));
	while(heap.empty() == false) {
		Pair top = heap.top();
		heap.pop();
		if(visited[top.vertex]) continue;
//		cout<<"visiting "<<top.vertex<<endl;
		visited[top.vertex] = true;
		for(int_t i = 0; i < graph[top.vertex].size(); i++) {
			Edge& edge = graph[top.vertex][i];
			if(dis[edge.to] > dis[top.vertex] + edge.weight) {
				dis[edge.to] = dis[top.vertex] + edge.weight;
				heap.push(Pair(dis[edge.to],edge.to));
				count[edge.to] = count[top.vertex];
			} else if(dis[edge.to] == dis[top.vertex] + edge.weight) {
				count[edge.to] += count[top.vertex];
			}
		}
	}
}
int_t weight[LARGE + 1][LARGE + 1];
int main() {
	memset(weight,0x7f,sizeof(weight));
	cin >> n >> m;
	for(int_t i = 1; i <= m; i++) {
		int_t from,to,weight;
		cin >> from >> to >> weight;
		if(weight < ::weight[from][to]){
			pushEdge(from,to,weight);
			::weight[from][to] = weight;
		}
		
	}
//	for(int_t i = 1; i <= n; i++) {
//		std::sort(graph[i].begin(),graph[i].end());
//		std::vector<Edge>& curr = graph[i];
//		curr.resize(std::unique(curr.begin(),curr.end()) - curr.begin());
//	}
	Dijkstra();
	if(dis[n] >= INF) {
		cout <<"No answer";
	} else
		cout << dis[n] << " " << count[n] << endl;
	return 0;
}