Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stdlib.h>
- #include <string.h>
- #define MAX 250000
- #define INF 100000009
- std::vector<int> A[MAX];
- std::vector<int> c[MAX];
- int n, m;
- int s[105], K;
- int d[105][10005]; // key
- int node[105][10005]; // gia tri node
- int idx[105][10005]; // index cua node tuong ung trong array
- int sH; // size of array
- bool fixed[105][10005];
- int iS;
- int result;
- void output () {
- printf("%d\n", result);
- }
- void swap(int i, int j) {
- int tmp = node[iS][i];
- node[iS][i] = node[iS][j];
- node[iS][j] = tmp;
- idx[iS][node[iS][i]]=i;
- idx[iS][node[iS][j]]=j;
- }
- void upHeap(int i) {
- if(i == 0) return;
- while(i > 0) {
- int pi = (i-1)/2;
- if(d[iS][node[iS][i]] < d[iS][node[iS][pi]]) {
- swap(i,pi);
- }
- else {
- break;
- }
- i = pi;
- }
- }
- void downHeap(int i) {
- int L = 2*i + 1;
- int R = 2*i + 2;
- int maxIdx = i;
- if(L < sH && d[iS][node[iS][L]] < d[iS][node[iS][maxIdx]]) maxIdx = L;
- if(R < sH && d[iS][node[iS][R]] < d[iS][node[iS][maxIdx]]) maxIdx = R;
- if(maxIdx != i) {
- swap(i, maxIdx);
- downHeap(maxIdx);
- }
- }
- void insert(int v, int k) {
- d[iS][v] = k;
- node[iS][sH] = v;
- idx[iS][node[iS][sH]] = sH;
- upHeap(sH);
- sH++;
- }
- bool inHeap(int v) {
- if(idx[iS][v] >= 0) return true;
- else return false;
- }
- void updateKey(int v, int k) {
- if(d[iS][v] > k) {
- d[iS][v] = k;
- upHeap(idx[iS][v]);
- }
- else {
- d[iS][v] = k;
- downHeap(idx[iS][v]);
- }
- }
- int deleteMin() {
- int sel_node = node[iS][0];
- swap(0, sH-1);
- sH--;
- downHeap(0);
- return sel_node;
- }
- void dijkstra (int x) {
- sH = 0;
- for(int v=1; v <= n; ++v) {
- fixed[iS][v] = false;
- idx[iS][v] = -1;
- }
- d[iS][x] = 0;
- fixed[iS][x] = true;
- for(int i=0; i < A[x].size(); ++i) {
- int v = A[x][i];
- insert(v,c[x][i]);
- }
- while(sH > 0) {
- int u = deleteMin();
- fixed[iS][u] = true;
- for(int i=0; i < A[u].size(); ++i) {
- int v = A[u][i];
- if(fixed[iS][v]) continue;
- if(!inHeap(v)) {
- int w = d[iS][u] + c[u][i];
- insert(v,w);
- }
- else {
- if(d[iS][v] > d[iS][u] + c[u][i])
- updateKey(v, d[iS][u] + c[u][i]);
- }
- }
- }
- }
- void solve() {
- memset(d, 0, sizeof(d));
- memset(node, 0, sizeof(node));
- memset(idx, 0, sizeof(idx));
- memset(fixed, 0, sizeof(fixed));
- iS = 1;
- for (int i = 1; i <= K; ++i) {
- dijkstra(s[i]);
- ++iS;
- }
- result = -INF;
- for (int i = 1; i <= K-1; ++i) {
- for (int j = i + 1; j <= K; ++j) {
- if (result < d[i][s[j]])
- result = d[i][s[j]];
- }
- }
- }
- void input() {
- scanf("%d%d", &n, &m);
- int u,v,w;
- for(int i=1; i <= m; i++) { // Take Edges
- scanf("%d%d%d", &u, &v, &w);
- A[u].push_back(v);
- A[v].push_back(u);
- c[u].push_back(w);
- c[v].push_back(w);
- }
- scanf("%d", &K);
- for (int i = 1; i <= K; ++i) {
- scanf("%d", &s[i]);
- }
- }
- // Driver code
- int main() {
- // freopen("inp", "r", stdin);
- // freopen("out", "w", stdout);
- input();
- solve();
- output();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement