Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 求解为什么TLE？

Posted by sdfzyhx at 2016-02-25 17:45:38 on Problem 2449
```#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct sit
{
int p,dis,val;
}s1,s2;
int first[1010],next[100010],length[100010],to[100010],f[1010],
first2[1010],next2[100010],to2[100010],time[1010];
bool b[1010];
struct cmp
{
bool operator()(const sit &a,const sit &b)
{
return a.val>b.val;
}
};
priority_queue<sit,vector<sit>,cmp> q;
int main()
{
int i,j,k,l,m,n,p,x,y,z,s,t,min;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
next[i]=first[x];
first[x]=i;
length[i]=z;
to[i]=y;
next2[i]=first[y];
first2[y]=i;
to2[i]=x;
}
scanf("%d%d%d",&s,&t,&k);
memset(f,0x42,sizeof(f));
f[t]=0;
for (i=1;i<=n;i++)
{
p=-1;
min=0x7f7f7f7f;
for (j=1;j<=n;j++)
if (f[j]<min&&!b[j])
{
p=j;
min=f[j];
}
if (p==-1) break;
b[p]=1;
for (j=first2[p];j;j=next2[j])
if (f[to2[j]]>f[p]+length[j])
f[to2[j]]=f[p]+length[j];
}
s1.p=s;
s1.dis=0;
s1.val=f[s];
q.push(s1);
if(s==t) k++;
while (!q.empty())
{
s1=q.top();
printf("p=%d dis=%d val=%d\n",s1.p,s1.dis,s1.val);
q.pop();
if (++time[s1.p]==k)
{
printf("%d\n",s1.val);
return 0;
}
for (i=first[s1.p];i;i=next[i])
{
s2.p=to[i];
s2.dis=s1.dis+length[i];
s2.val=s2.dis+f[s2.p];
q.push(s2);
}
}
printf("-1\n");
}```

Followed by: