rt,第七个点WA了,下载数据显示运行错误,可已经开了双倍空间啊
代码如下
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n,p,lk[2510],hp = 0,u,v,ppp,dist[2510],s,t,vis[2510];
struct sth
{
int pow,wei,power;
}e[15000];
struct node
{
int user,dis;
bool operator < (const node &x) const
{
return x.dis < dis;
}
};
priority_queue <node> q;
void add(int xx,int yy,int pp)
{
e[++hp] = {yy,lk[xx],pp};
lk[xx] = hp;
}
void dij()
{
while (!q.empty())
{
node sum = q.top();
//printf("%d ",sum.user);
q.pop();
for (int i = lk[sum.user];i;i = e[i].wei)
{
if (dist[sum.user] + e[i].power < dist[e[i].pow])
{
dist[e[i].pow] = dist[sum.user] + e[i].power;
if (!vis[e[i].pow])
{
vis[e[i].pow] = 1;
q.push({e[i].pow,dist[e[i].pow]});
}
}
}
}
}
int main()
{
scanf("%d %d %d %d",&n,&p,&s,&t);
memset(dist,0x3f,sizeof(dist));
dist[s] = 0;vis[s] = 1;
for (int i = 1;i <= p;i++)
{
scanf("%d %d %d",&u,&v,&ppp);
add(u,v,ppp);add(v,u,ppp);
}
// printf("%d %d %d %d",n,p,s,t);
q.push({s,0});
// printf("%d",q.top().user);
dij();
printf("%d",dist[t]);
}