1. Dijkstra算法
   這個(gè)算法和prime求最小生成樹(shù)特別像，都是找到最小邊，把點(diǎn)加進(jìn)來(lái)，然后用新加的點(diǎn)更新其他沒(méi)有被加進(jìn)來(lái)的點(diǎn)。
   1.
      #define N 1002
   2.
      #define MAX 99999
   3.
      int edges[N][N],d[N],n;
   4.
       
   5.
      void dijkstra(int v)
   6.
      {
   7.
              int i,j;
   8.
              bool s[N]={false};
   9.
              for(i=1;i<=n;i++)
  10.
                      d[i]=edges[v][i];
  11.
              d[v]=0;s[v]=true;
  12.
              for(i=1;i<n;i++)
  13.
              {
  14.
                      int temp=MAX;
  15.
                      int u=v;
  16.
                      for(j=1;j<=n;j++)
  17.
                              if((!s[j])&&(d[j]<temp))
  18.
                              {
  19.
                                      u=j;
  20.
                                      temp=d[j];
  21.
                              }
  22.
                              s[u]=true;
  23.
                              for(j=1;j<=n;j++)
  24.
                                      if((!s[j])&&(edges[u][j]<MAX)&&(d[u]+edges[u][j])<d[j])
  25.
                                              d[j]=d[u]+edges[u][j];
  26.
              }
  27.
       
  28.
      }

2. SPFA算法 （shortest path faster algorithm）
    不斷維護(hù)一個(gè)隊(duì)列，如果隊(duì)列里的點(diǎn)，使得其他點(diǎn)的最短路得到松弛，則這個(gè)點(diǎn)還有可能使另外的點(diǎn)松弛，所以如果這個(gè)點(diǎn)不在隊(duì)列里，就把它入隊(duì)。
    很多時(shí)候，給定的圖存在負(fù)權(quán)邊，這時(shí)類似Dijkstra等算法便沒(méi)有了用武之地，而B(niǎo)ellman-Ford算法的復(fù)雜度又過(guò)高，SPFA算法便派上用場(chǎng)了。 此算法時(shí)間復(fù)雜度為O（2*E），E為邊數(shù)。
 //pku1860 
    #include<stdio.h>
    #include<string.h>
    #include<vector>
    #define N 120
    using namespace std;
    struct Point
    {
        int id;
        double r, c;
    };
    vector<Point> p[N];
    int q[N],n,m,S,visit[N];
    double V,dist[N];
    int spfa()
    {
        memset(visit, 0, sizeof(visit));
        int i,j,head=0,tail=1,x;
        for(i=1; i<=n ;i++)
            dist[i]=0;    //此題是求換得的貨幣最多，所以初值賦0；
                          //若求最短路，初值應(yīng)賦為無(wú)窮大
        if(V<=0) return 0;
        q[0]=S;
        dist[S]=V;        //S為源，若求最短路，則dist[S]=0;
        visit[S]=1;
        while(head!=tail){ // Attention！！！由于對(duì)隊(duì)列長(zhǎng)度取模了，所以head<tail不一定成立，應(yīng)改為head!=tail
            x=q[head];
            visit[x]=0;
            head=(head+1)%N;
            for(i=0; i<p[x].size(); i++){

                j=p[x][i].id;
                if(dist[j]<(dist[x]-p[x][i].c)*p[x][i].r){
                    dist[j]=(dist[x]-p[x][i].c)*p[x][i].r;
                    if(!visit[j]){
                        q[tail]=j;
                        tail=(tail+1)%N;
                        visit[j]=1; //若如果j點(diǎn)的最短路徑估計(jì)值有所調(diào)整，
                                    // 且j點(diǎn)不在當(dāng)前的隊(duì)列中，就將j點(diǎn)放入隊(duì)尾
                    }
                }
            }
            if(dist[S]>V) return 1;
        }
        return 0;
    }
    int main()
    {
        int i,j,a,b;
        double rab, cab, rba, cba;
        Point p1, p2;
        while(scanf("%d %d %d %lf",&n, &m, &S, &V)!=EOF){
            for(i=1; i<=n; i++)
                p[i].clear();
        for(i=0; i<m; i++){
            scanf("%d %d %lf %lf %lf %lf",&a, &b, &rab, &cab, &rba, &cba);
            p1.id=b; p1.r=rab; p1.c=cab;
            p2.id=a; p2.r=rba; p2.c=cba;
            p[a].push_back(p1);
            p[b].push_back(p2);
        }
        j=spfa();
        if(j)
            printf("YES\n");
        else
            printf("NO\n");
        }
        return 0;
    }