Amit and his wife Shweta are in Singapore for their honeymoon. Shweta wants to visit every hotel present there. Amit and Shweta are in their hotel and Amit is planning out how can he fulfill Shweta’s wish.
There are N hotels there(they are staying at the hotel No. 1). There are exactly M roads connecting those hotels (It is guaranteed that any hotel can be visited from any other by roads). Each road has its length. Every day the couple visits exactly one unvisited hotel and come back. Amit wants to take the shortest distance to get to any hotel from his hotel(they use the same path to get back to their hotel).
But there is a problem, Singapore government has announced that the tourists have to choose N-1 roads to move in the city i.e Amit has to choose total N-1 roads such that they can visit all the other hotels. Also, path taken to reach any other hotel from their hotel should be the shortest. So in how many ways can Amit choose such N-1 roads.
The first line contains the number of test cases T. Then T test cases follow.
The first line of each test cases contains N and M, the number of hotels and roads respectively.
Next M lines contain A B C which denotes that there is a road of length C between hotels A and B.
The couples are staying in Hotel No. 1.
Print the number of ways modulo
Solution with Description
Given a connected graph with N nodes and M edges, you need to find the number of distinct trees that can be formed containing all N nodes from the given graph by removing edges such that the distance between the 1st and i th node in the tree is same as the shortest path distance between the 1st and i th node in the graph, for all i.
Try to think this using Dijkstra. See here .
In Dijkstra, we get the smallest distance from 1 to all the nodes. While updating the shortest distance of adjacent nodes of node K, also update the number of roads(cnt[adjacent node]) which directly lead to it with that distance. So if the shortest distance is same as before then we just add 1 to cnt[adjacent node] whereas if shortest distance changes then cnt[adjacent node] is made 1. Like in the sample test case: At first node 1 has a shortest distance 0. But all other nodes had the shortest distance infinite and the number of roads leading to 2 and 3 with this distance is 0. We take 1 as visited and update its adjacent nodes i.e. now the shortest distance of node 2 is 1 and node 3 is 2 and the number of roads leading to 2 and 3 with this distance is 1(cnt=cnt=1). Then node 2 is taken as visited and its adjacent node 3 can be reached with the same shortest distance 2, and we have to update the number of roads leading to node 3 with this shortest distance to 2(cnt=2). And now we take node 3.
Then the number of ways in which the tree can be constructed is the product of cnt[i] for all i.
Expected Time Complexity: O((N + M)*log(N)) per test case
typedef long long ll;
using namespace std;
ll minT = 1;
ll maxT = 10;
ll minN = 1;
ll maxN = 1000;
ll minM = 0;
ll maxM = 1e5;
ll minC = 1;
ll maxC = 1000;
ll mod = 1e9 + 7;
const int max_n = 1100;
ll inf = 1e15;
bool operator() (const pair<ll, ll> &a, const pair<ll, ll> &b)
return (a.first > b.first);
vector<pair<ll, ll> > v[max_n];
ll cnt[max_n], minDis[max_n];
priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, compare > pq;
ll t, i, j, n, m, ans, chVer, chDis, nextVer, nextDis, a, b, c, siz;
pair<ll, ll> tempPr;
assert(t>=minT && t<=maxT);
scanf("%lld %lld", &n, &m);
assert(n>=minN && n<=maxN);
assert(m>=minM && m<=maxM);
minDis[i] = inf;
cnt[i] = 0LL;
visited[i] = false;
scanf("%lld %lld %lld", &a, &b, &c);
assert(a>=minN && a<=maxN && a<=n);
assert(b>=minN && b<=maxN && b<=n);
assert(c>=minC && c<=maxC);
minDis = 0LL;
tempPr = pq.top();
nextDis = tempPr.first;
nextVer = tempPr.second;
if(nextDis == inf)
//printf("nextVer = %lld nextDis= %lld\n", nextVer, nextDis);
if(nextDis == minDis[nextVer])
visited[nextVer] = true;
siz = v[nextVer].size();
chDis = v[nextVer][j].first;
chVer = v[nextVer][j].second;
if(minDis[nextVer]+chDis <= minDis[chVer])
minDis[chVer] = minDis[nextVer]+chDis;
ans = 1LL;
//printf("cnt[%lld] = %lld\n", i, cnt[i]);
ans = (ans * cnt[i])%mod;