模板:最短路
//Floyd:(任意两点间的最短路问题)for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); //Dijkstra(无负边时的最短路问题)const int INF = 0x3f3f3f3f;const int N = 111111; vector < pair < int,int > >E[N];int n,m;int d[N]; void init() { for (int i = 0; i < N; i++) d[i] = INF; for (int i = 0; i < N; i++) E[i].clear();} void dijkstra(int s, int d[]) { priority_queue < pair < int, int > >Q; d[s] = 0; Q.push(make_pair( - d[s], s)); while (!Q.empty()) { int now = Q.top().second; Q.pop(); for (int i = 0; i < E[now].size(); i++) { int v = E[now][i].first; int D = d[now] + E[now][i].second; if (d[v] > D) { d[v] = D; Q.push(make_pair( - d[v], v)); } } }}
来源: http://www.bubuko.com/infodetail-2350967.html