Holy Grail Bellman-Ford/spfa

Holy Grail

Bellman-Ford

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = , maxm = ;

 const int inf = 0x3f3f3f3f;

 struct edge {

     int v, w;

 };

 vector<edge> maps[maxn];

 int dis[maxn], n, m;

 bool BellmanFord(int s) {  // s为源点

     fill(dis, dis+n, inf);

     dis[s] = ;

     for (int i = ; i < n-; i++) {

         for (int u = ; u < n; u++) {

             for (int j = ; j < maps[u].size(); j++) {

                 int v = maps[u][j].v;

                 int w = maps[u][j].w;

                 if (dis[u] + w < dis[v]) {

                     dis[v] = dis[u] + w;

                 }

             }

         }

     }

     for (int u = ; u < n; u++) {

         for (int j = ; j < maps[u].size(); j++) {

             int v = maps[u][j].v;

             int w = maps[u][j].w;

             if (dis[u] + w < dis[v])

                 return false;

         }

     }

     return true;

 }

 int main() {

     int t; scanf("%d",&t);

     while (t--) {

         scanf("%d%d",&n,&m);

         for (int i = ; i < n; i++) maps[i].clear();

         for (int i = ; i <= m; i++) {

             int u, v, w; scanf("%d%d%d",&u,&v,&w);

             maps[u].push_back(edge{v,w});

         }

         for (int i = ; i <= ; i++) {

             int u, v; scanf("%d%d",&u,&v);

             bool flag = BellmanFord(v);

             printf("%d\n",-dis[u]);

             //if (flag == false) continue;

             maps[u].push_back(edge{v,-dis[u]});

         }

     }

 }

spfa

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = , maxm = ;

 struct edge {

     int v, w;

 };

 vector<edge> maps[maxn];

 int dis[maxn], n, m;

 bool vis[maxn];

 void add(int u, int v, int w) {

     maps[u].push_back(edge{v,w});

 }

 void spfa(int s) {

     memset(dis, 0x3f3f3f3f, sizeof(dis));

     memset(vis,,sizeof(vis));

     queue<int> que;

     que.push(s), dis[s] = , vis[s] = true;

     while(!que.empty()) {

         int u = que.front();

         que.pop();

         vis[u] = false;

         for(int i = ; i < maps[u].size(); i++) {

             int v = maps[u][i].v;

             int w = maps[u][i].w;

             if(dis[v] > dis[u]+w) {

                 dis[v] = dis[u] + w;

                 if(vis[v] == false) {

                     que.push(v);

                     vis[v] = true;

                 }

             }

         }

     }

 }

 int main() {

     int t; scanf("%d",&t);

     while(t--) {

         scanf("%d%d",&n,&m);

         for (int i = ; i < n; i++) maps[i].clear();

         for(int i = ; i <= m; i++) {

             int u, v, w; scanf("%d%d%d",&u,&v,&w);

             add(u,v,w);

         }

         for(int i = ; i <= ; i++) {

             int u, v; scanf("%d%d",&u,&v);

             spfa(v);

             add(u,v,-dis[u]);

             printf("%d\n",-dis[u]);

         }

     }

     return ;

 }