终于从SPFA转到了dij堆优化

spfa优化

唉，head和next数组的大小应该和边相同啊......

回复 @Turkey :
建议全敲堆优化迪杰斯塔，最稳定了....

第一发堆优化dijkstra
最短路全在这水的

多好的模板题见证了我从矩阵到编表到前向星
从迪杰斯特拉到spfa

FIB-HEAP捂脸
PAIR-HEAP捂脸

2000分纪念！！撒花~~

inline 加速光环^_^...

真科学，边表80，邻接矩阵100。。。

好神奇，前8个点全过，最后两个一个W一个T。。。

回复 @--<-<-< :
直接贴代码真的好么

回复 @真神名曰驴蛋�� :
No zuo no die why you try
You try you die 怪 我 咯

Openjudge上没事，这边卡= =；
求助

回复 @智霞Forever :
#include<iostream>
#include<cstdlib>
#include<queue>
#include<cstdio>
#include<ctime>
#include<cstdio>
#include<cstring>
const int maxn=110;
int m,n,len=0,head[maxn],dis[maxn][maxn];
const int maxe=maxn*maxn;
using namespace std;
struct node
{
int num,dis;
node(){};
node(int a,int b)
{
num=a,dis=b;
}
bool operator < (const node&a)const
{
return dis>a.dis;
}
};
struct Edge
{
int dis,to,next;
}e[maxe];
void Dijs(int);
void Init();
void Insert(int,int,int);
int main()
{
Init();
Dijs(0);
//while(1);
return 0;
}
void Init()
{
memset(head,-1,sizeof(head));
memset(dis,0,sizeof(dis));
memset(e,0,sizeof(e));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
Insert(x,y,z);
Insert(y,x,z);
}
}
void Insert(int x,int y,int z)
{
len++;
e[len].to=y;
e[len].dis=z;
e[len].next=head[x];
head[x]=len;
}
void Dijs(int x)
{
int d[maxn];
memset(d,0x7f,sizeof(d));
bool f[maxn]={0};
priority_queue<node> q;
d[x]=0;
q.push(node(x,d[x]));
while(!q.empty())
{
node temp=q.top();q.pop();
int k=temp.num;
f[k]=1;
for(int i=head[k];i!=-1;i=e[i].next)
{
int j=e[i].to;
if(!f[j]&&d[j]>d[k]+e[i].dis)
{
d[j]=d[k]+e[i].dis;
q.push(node(j,d[j]));
}
}
}
for(int i=0;i<n;i++)
{
dis[x][i]=d[i];
}
}

回复 @智霞Forever :
#include<iostream>
#include<cstdlib>
#include<queue>
#include<cstdio>
#include<ctime>
#include<cstdio>
#include<cstring>
const int maxn=110;
int m,n,len=0,head[maxn],dis[maxn][maxn];
const int maxe=maxn*maxn;
using namespace std;
struct node
{
int num,dis;
node(){};
node(int a,int b)
{
num=a,dis=b;
}
bool operator < (const node&a)const
{
return dis>a.dis;
}
};
struct Edge
{
int dis,to,next;
}e[maxe];
void Dijs(int);
void Init();
void Insert(int,int,int);
int main()
{
Init();
Dijs(0);
//while(1);
return 0;
}
void Init()
{
memset(head,-1,sizeof(head));
memset(dis,0,sizeof(dis));
memset(e,0,sizeof(e));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
Insert(x,y,z);
Insert(y,x,z);
}
}
void Insert(int x,int y,int z)
{
len++;
e[len].to=y;
e[len].dis=z;
e[len].next=head[x];
head[x]=len;
}
void Dijs(int x)
{
int d[maxn];
memset(d,0x7f,sizeof(d));
bool f[maxn]={0};
priority_queue<node> q;
d[x]=0;
q.push(node(x,d[x]));
while(!q.empty())
{
node temp=q.top();q.pop();
int k=temp.num;
f[k]=1;
for(int i=head[k];i!=-1;i=e[i].next)
{
int j=e[i].to;
if(!f[j]&&d[j]>d[k]+e[i].dis)
{
d[j]=d[k]+e[i].dis;
q.push(node(j,d[j]));
}
}
}
for(int i=0;i<n;i++)
{
dis[x][i]=d[i];
}
}

为啥自己测样例就对了，提上去就错= =

注意是无向图，边表要开到最大边数的两倍。

2500个城镇看成1500个了。。。