struct edge{
int to,next,w;
edge(){}
edge(int to,int next,int w){
this->to=to,this->next=next,this->w =w;
}
};E[maxc<<1];
int first[maxp],np,dist[maxp];
bool vis[mxap];
int inqc[mxap];
struct Data{
int i,v;
Data(){};
Data(int i,int v){
this->i =i,this->v =v;
}
friend bool operator <(const Data &a,const Data &b){
return a.v >b.v ;
}
};
void dijkstra(int s){
for(int i=1;i<=P;i++){//P是节点个数
dist [i]=inf,vis[i]=0;
}
priority_queue<Data> pq;
dist[s]=0;
pq.push(Data(s,dist[s]));
while(!pq.empty()){
Data tmp =pq.top();pq.pop();
int i=tmp.i ,v=tmp.v ;
if(vis[i])continue;
vis[i]=1;
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(dist[i]+E[p].w<dist[j]){
dist[j]=dist[i]+E[p].w;
pq.push(Data(j,dist[j]));
}
}
}
}
int SPFA(int s){
for(int i=1;i<=P;i++){
dist[i]=inf,vis[i]=0,inqc[i]=0;
}
queue<int> q;
dist[s]=0;
q.push(s);
vis[s]=1,inqc[s]++;
while(!q.empty()){
int i=q.front();q.pop;
vis[i]=0;
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(dist[i]+E[p].w<dist[j]){
dist[j]=dist[i]+E[p].w;
if(!vis[j]){
if(inqc[j]==P-1)return 0;
vis[j]=1,inqc[j]++,q,push(j);
}
}
}
}
return 1;
}