最短路（Dijkstra+Priority_queue+鄰接表）
struct NODE
{
int to;
int len;
bool operator<(const NODE& cmp ) const{return cmp.len };
void dijkstra(int n,vector buf[],int s,int* min)
{
int i;
NODE v;
for (i=0;i min[i]=INF,vis[i]=false;
for ( i=0 ; 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 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 dis[i]=INF;
for ( i=0 ; i
struct NODE
{
int to;
int len;
bool operator<(const NODE& cmp ) const{return cmp.len
void dijkstra(int n,vector
{
int i;
NODE v;
for (i=0;i
for ( i=0 ; 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
{
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
for ( i=0 ; i
inqueue[i]=false;
dis[s]=0;
head=tail=0;
que[tail++]=s;
inqueue[s]=true;
while(head
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;
}
}
}
}
第二個(gè)SPFA是從網(wǎng)上找來的修改了一下，因?yàn)樽隽藀oj1511,所以把鄰接表用前向星的形式寫了，題目中的數(shù)據(jù)大的變態(tài)。。。1<=V,E<=1000000，考試大建議都開成全局變量，然后盡量少用形參。
但是一般情況下，用vector表示鄰接表方便點(diǎn)。