qq_25759917 2022-04-14 11:17 采纳率: 72.7%
浏览 22
已结题

洛谷P4779最短路径问题TLE

img

#include<bits/stdc++.h>
using namespace std;
int a[10005][10005];
int d[10005],i,j;
const int INF=1e9;
int t;
int read()
{
int x=0,y=1;
char c;
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*y;
}
void dij(int n)//单源最短路径
{
bool f[10005]={0};
f[1]=1;
int v;
for(i=1;i<n;i++)
{
int min=INF;
for(j=1;j<=n;j++)
{
if(!f[j]&&min>d[j])//找未标记中最小的
{
min=d[j];
v=j;
}
}
f[v]=1;//标记
for(j=v;j<=n;j++)
{
if(!f[j]&&a[v][j]+d[v]<d[j])//更新路径长度
{
d[j]=a[v][j]+d[v];
}
}
}
}

int main()
{
int n,m,x,y,z;
n=read(),m=read(),t=read();
for(i=1;i<=m;i++)
{
x=read(),y=read(),z=read();
a[x][y]=z;
}
for(i=1;i<=n;i++)
{
d[i]=a[t][i];//路径长度初始化]]
}
dij(n);
for(i=1;i<=n;i++)
{
printf("%d\n",d[i]);
}
return 0;
}
爆TLE,请问这个程序哪里出了问题?

  • 写回答

1条回答

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 系统已结题 4月22日
      • 已采纳回答 4月14日
      • 创建了问题 4月14日

      悬赏问题

      • ¥15 不使用zk实现双机clickhouse、kafka数据同步
      • ¥15 使用Labwindows/CVI程控万用表时自动切换量程
      • ¥15 Matlab修改xml参数后允许不了exe文件
      • ¥15 Java的问题解答一下呗
      • ¥20 怎么将vs中的程序同步到sql中的表中
      • ¥15 用flask框架接收前端上传的文本文件后怎么读取该文件
      • ¥15 有没有嵌入式ubuntu的朋友
      • ¥50 diddler Burp Suite
      • ¥20 关于UE5.1的问题,求专家解答!
      • ¥30 关于#爬虫#的问题:百度为您找到相关结果约100,000,000个 但只展现70页 有没有可能提取出来全部的搜索结果