1. Dijkstra算法
这个算法和prime求最小生成树特别像，都是找到最小边，把点加进来，然后用新加的点更新其他没有被加进来的点。
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）
不断维护一个队列，如果队列里的点，使得其他点的最短路得到松弛，则这个点还有可能使另外的点松弛，所以如果这个点不在队列里，就把它入队。
很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 此算法时间复杂度为O（2*E），E为边数。
//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；
//若求最短路，初值应赋为无穷大
if(V<=0) return 0;
q[0]=S;
dist[S]=V; //S为源，若求最短路，则dist[S]=0;
visit[S]=1;
while(head!=tail){ // Attention！！！由于对队列长度取模了，所以head<tail不一定成立，应改为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点的最短路径估计值有所调整，
// 且j点不在当前的队列中，就将j点放入队尾
}
}
}
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;
}