洛谷 P1608 路径统计

题目传送门

最短路计数的板子,存个堆优化的Dijkstra.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

int n,m,head[2001],ans[2001],tot;
bool vis[2001],dp[2001][2001];//处理重边 
struct kkk {
	int to,next,len;
}e[4000001];
struct node {
	int id,di;
	node() {
		di = 2099999999;
	}
	bool operator <(const node &s) const {
		return di > s.di;
	}
}d[2001];
priority_queue<node> q;

inline void add(int x,int y,int z) {
	e[++tot].to = y;
	e[tot].len = z;
	e[tot].next = head[x];
	head[x] = tot;
}

inline void dij() {
	memset(vis,0,sizeof(vis));
	d[1].di = 0;d[1].id = 1;
	q.push(d[1]);
	ans[1] = 1;
	while(!q.empty()) {
		node u = q.top();
		q.pop();
		if(vis[u.id]) continue;
		vis[u.id] = 1;
		for(int i = head[u.id];i; i = e[i].next) {
			int v = e[i].to;
			if(d[v].di > d[u.id].di + e[i].len) {
				d[v].di = d[u.id].di + e[i].len;
				ans[v] = ans[u.id];
				dp[u.id][v] = 1;
				d[v].id = v;
				q.push(d[v]);
			}
			else if(d[v].di == d[u.id].di + e[i].len && !dp[u.id][v]) {
					ans[v] += ans[u.id],dp[u.id][v] = 1;
			}
		}
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m; i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	dij();
	if(d[n].di < 1000000000) printf("%d %d",d[n].di,ans[n]);
	else printf("No answer");
	
	return 0;
}