最短路（Dijkstra+Priority_queue+邻接表）
struct NODE
{
int to;
int len;
bool operator<(const NODE& cmp ) const{return cmp.len<len;}
};
void dijkstra(int n,vector<NODE> buf[],int s,int* min)
{
int i;
NODE v;
for (i=0;i<n;i++)
min[i]=INF,vis[i]=false;
for ( i=0 ; i<buf[s].size() ; i++ )
{
min[buf[s][i].to]=buf[s][i].len;
que.push(buf[s][i]);
}
vis[s]=true;
while (!que.empty())
{
v=que.top();que.pop();vis[v.to]=true;
for ( i=0 ; i<buf[v.to].size() ; i++ )
if ( !vis[buf[v.to][i].to] && min[buf[v.to][i].to]>min[v.to]+buf[v.to][i].len )
{
que.push(buf[v.to][i]);
min[buf[v.to][i].to]=min[v.to]+buf[v.to][i].len;
}
}
}
最短路（SPFA+正向表）
Const int INF = 1000000000;
struct NODE
{
int to;
int len;
struct NODE *next;
};
void SPFA( NODE* mat[] , int P , int s , int dis[] )
{
int i,x,head,tail;
NODE* tp;
for(i=0;i<P;i++)
dis[i]=INF;
for ( i=0 ; i<P ; i++ )
inqueue[i]=false;
dis[s]=0;
head=tail=0;
que[tail++]=s;
inqueue[s]=true;
while(head<tail)
{
x=que[head++];
inqueue[x]=false;
for( tp=mat[x] ; tp ; tp=tp->next )
if( dis[tp->to] > dis[x]+tp->len )
{
dis[tp->to]=dis[x]+tp->len;
if(!inqueue[tp->to])
{
que[tail++]=tp->to;
inqueue[tp->to]=true;
}
}
}
}
第二个SPFA是从网上找来的修改了一下，因为做了poj1511,所以把邻接表用前向星的形式写了，题目中的数据大的变态。。。1<=V,E<=1000000，青年人网建议都开成全局变量，然后尽量少用形参。
但是一般情况下，用vector表示邻接表方便点。
责任编辑：小草
