Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
using namespace std;
typedef long long int lint;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
const int N = 100100;
int n;
vector<pil> edges[N];
pll add(pll a, pll b) {
if (a.first != b.first) return min(a,b);
return pll(a.first,(a.second+b.second)%mod);
}
pll mul(pll a,pll b){
return pll(a.first+b.first,a.second*b.second%mod);
}
/*
* edges に辺の情報(終点、距離)を入れると、(sからの最短距離,最短距離の道の本数%mod)を保持する vector を返す。
*/
vector<pll> calc(int s) {
vector<pll> dp(n, pll(inf, 0));
vector<bool> vis(n, false);
priority_queue<pli, vector<pli> , greater<pli> > que;
dp[s] = pll(0, 1);
que.push(pli(0, s));
while (not que.empty()) {
pli vd = que.top(); que.pop();
int v = vd.second;
if (vis[v]) continue;
vis[v] = true;
REP(i, 0, edges[v].size()) {
pil wc = edges[v][i];
int w = wc.first;
lint c = wc.second;
dp[w]=add(dp[w],mul(dp[v],pll(c,1)));
que.push(pli(dp[w].first,w));
}
}
return dp;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.