poj 1860

单元最短路径问题
  1 #include <iostream>
  2 #include <string>
  3 #include <vector>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <map>
  7 #include <algorithm>
  8 #include <list>
  9 #include <ctime>
 10 #include <set>
 11 #include <string.h>
 12 #include <queue>
 13 #include <cstdio>
 14 using namespace std;
 15 typedef double typep;
 16 //int maxData = 0x3fffffff;
 17 double maxData = 0;
 18 
 19 bool relax(typep u, typep& v, typep w, typep com) {
 20     if (v < ((u - com) * w)) {
 21         v = ((u - com) * w);
 22         return true;
 23     } else
 24         return false;
 25 }
 26 
 27 bool bellman_ford(int s, vector<typep> &d, vector<vector<typep> > path,
 28         vector<vector<typep> > commssion) {
 29     int n = d.size();
 30     int i, j, k;
 31     bool judge;
 32 
 33     for (i = 0; i < n - 1; i++) {
 34         for (j = 0; j < n; j++) {
 35             for (k = 0; k < n; k++) {
 36                 judge = relax(d[j], d[k], path[j][k], commssion[j][k]);
 37             }
 38         }
 39     }
 40 
 41     for (j = 0; j < n; j++) {
 42         for (k = 0; k < n; k++) {
 43             judge = relax(d[j], d[k], path[j][k], commssion[j][k]);
 44             if (judge) {
 45                 return true;
 46             }
 47 
 48         }
 49     }
 50 
 51     return false;
 52 }
 53 
 54 bool SPFA(int s, vector<typep> &d, vector<vector<typep> > path,
 55         vector<vector<typep> > commssion) {
 56     int n = d.size();
 57     queue<int> myqueue;
 58     int i;
 59     vector<bool> final(n, false); //记录顶点是否在队列中，SPFA算法可以入队列多次
 60     vector<int> cnt(n, 0); //记录顶点入队列次数
 61     final[s] = true;
 62     cnt[s]++; //源点的入队列次数增加
 63     myqueue.push(s);
 64     int topint;
 65     bool judge;
 66     while (!myqueue.empty()) {
 67         topint = myqueue.front();
 68         myqueue.pop();
 69         final[topint] = false;
 70         for (i = 0; i < n; ++i) {
 71             if (d[topint] > maxData) {
 72                 judge = relax(d[topint], d[i], path[topint][i],
 73                         commssion[topint][i]);
 74                 if (judge) {
 75                     if (!final[i]) { //判断是否在当前的队列中
 76                         final[i] = true;
 77                         cnt[i]++;
 78                         if (cnt[i] >= n) //当一个点入队的次数>=n时就证明出现了负环。
 79                             return true;
 80                         myqueue.push(i);
 81                     }
 82                 }
 83             }
 84         }
 85     }
 86     return false;
 87 }
 88 
 89 int main() {
 90     int n, m, s;
 91     double v;
 92     scanf("%d %d %d %lf", &n, &m, &s, &v);
 93     s--;
 94     vector<vector<typep> > path(n, vector<typep>(n, maxData));
 95     vector<vector<typep> > commssion(n, vector<typep>(n, maxData));
 96     int a, b;
 97     double rab, cab, rba, cba;
 98     for (int i = 0; i < m; i++) {
 99         scanf("%d %d %lf %lf %lf %lf", &a, &b, &rab, &cab, &rba, &cba);
100         a--;
101         b--;
102         path[a][b] = rab;
103         path[b][a] = rba;
104         commssion[a][b] = cab;
105         commssion[b][a] = cba;
106     }
107     vector<typep> d(n, maxData);
108     d[s] = v;
109 //    int judge = bellman_ford(s, d, path, commssion);
110     int judge = SPFA(s, d, path, commssion);
111     if (judge)
112         cout << "YES" << endl;
113     else
114         cout << "NO";
115     return 0;
116 
117 }
from kakamilan