华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1001|回复: 0
打印 上一主题 下一主题

P1339热浪Heat Wave

[复制链接]

4

主题

6

帖子

58

积分

华一学生

积分
58
跳转到指定楼层
楼主
发表于 2018-7-15 22:55:22 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
#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是怎么错的

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-11-2 08:20 , Processed in 0.100295 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表