华师一附中OI组

标题: P1339热浪Heat Wave [打印本页]

作者: 南望山 时间: 2018-7-15 22:55
标题: P1339热浪Heat Wave
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=0x7fffffff/3;
int t,c,ts,te;
int w[2510][2510];
int a[2510][2510];
int team[10000];
int dis[2510];
bool exist[2510];
int num[2510];
int main()
{
cin>>t>>c>>ts>>te;
for(int i=1; i<=2509; i++)
      for(int j=1; j<=2509; j++)
         w[i][j]=MAXN;
for(int i=0; i<=2509; i++)
      dis[i]=MAXN;
for(int i=1; i<=c; i++)
{
      int x,y,v;
      cin>>x>>y>>v;
      w[x][y]=w[y][x]=v;
      a[x][++num[x]]=y;
      a[y][++num[y]]=x;
}
/*
for(int i=1;i<=t;i++)
      cout<<num[i]<<endl;
*/
memset(team,0,sizeof(team));
memset(exist,0,sizeof(exist));
dis[ts]=0;
int head=0;
int tail=1;
exist[ts]=1;
do
{
      head++;
      head=(head-1)%2510+1;
      int u=team[head];
      exist[u]=0;
      for(int j=1; j<=num[u]; j++)
      {
         if(dis[a[u][j]]>dis[u]+w[u][a[u][j]])
         {
            dis[a[u][j]]=dis[u]+w[u][a[u][j]];
            if(!exist[a[u][j]])
            {
                  tail++;
                  tail=(tail-1)%2510+1;
                  team[tail]=a[u][j];
                  exist[a[u][j]]=1;
            }
         }
      }
}
while(head!=tail);
cout<<dis[te];
return 0;
}
SPFA是怎么错的

欢迎光临华师一附中OI组 (http://hsyit.cn/)