Dijkstra堆优化，然鹅：TLE

代码如下：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
using namespace std;

const int N = 1000010, MOD = 1e9 + 7;
typedef pair<int, int> PII;

int n, m;
bool st[N];
int dist[N], cnt[N];
vector<PII> g[N];
map<PII, int> mp;

void dijkstra()
{
	memset(dist, 0x3f, sizeof(dist));
	memset(cnt, 0, sizeof(cnt));
	dist[1] = 0;
	cnt[1] = 1;
	priority_queue<PII, vector<PII>, greater<PII> > q;
	for(int i = 1; i <= n; i++) q.push({dist[i], i});
	
	while(q.size())
	{
		PII t = q.top(); q.pop();
		int idx = t.second, w = t.first;
		if(st[idx]) continue;
		st[idx] = true;
		
		for(int i = 0; i < g[idx].size(); i++)
		{
			int tv = g[idx][i].second, tw = g[idx][i].first;
			
			if(dist[tv] > dist[idx] + tw)
			{
				dist[tv] = dist[idx] + tw;
				q.push({dist[tv], tv});
				cnt[tv] = (cnt[idx] * mp[{idx, tv}]) % MOD;
			}
			else if(dist[tv] == dist[idx] + tw)
			{
				cnt[tv] += (cnt[idx] * mp[{idx, tv}]) % MOD;
				cnt[tv] %= MOD;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		if(u != v)
		{
			if(!mp[{u, v}])
			{
				g[u].push_back({1, v});
				g[v].push_back({1, u});
			}
			++mp[{u, v}];
			++mp[{v, u}];
		}
	}
	dijkstra();
	for(int i = 1; i <= n; i++) cout << cnt[i] << endl;
	return 0;
}

$help$