record #172329419

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, m;
int dis[100010];
int vis[100010];
int cnt[100010];

struct node
{
	int x, d;
	
	bool operator < (const node & b) const
	{
		return d > b.d;
	}
} ;

struct edge
{
	int y, w; 
} ;

vector<edge> g[100010];

void add(int x, int y, int w)
{
	g[x].push_back((edge){y, w});
}

void dijkstra(int s)
{
	priority_queue<node> q;
	memset(dis, 0x3f, sizeof(dis));
	q.push((node){s, 0});
	dis[s] = 0;
	cnt[s] = 1;
	while (q.size())
	{
		node t = q.top();
		q.pop();
		int x = t.x;
		if (vis[x])
			continue;
		vis[x] = 1;
		for (int i = 0; i < g[x].size(); i++)
		{
			int y = g[x][i].y;
			int w = g[x][i].w;
			if (dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				cnt[y] = cnt[x];
				q.push((node){y, dis[y]});
			}
			else if (dis[y] == dis[x] + w)
				cnt[y] += cnt[x];
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
	}
	dijkstra(1);
	if (dis[n] != INF)
		cout << dis[n] << " " << cnt[n] << endl;
	else cout << "No answer" << endl;
	return 0;
}

help&thx