| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴个代码,谁帮看看,reIn Reply To:怎么老是runtime error啊?没几个re的啊。用邻接表+dfs做的,什么原因啊??? Posted by:djj2007 at 2008-05-10 14:01:41 #include <iostream>
#include <vector>
const int INF = 1<<29;
using namespace std;
struct Node
{
int v;
int b,e,c;
struct Node *next;
Node()
{
next = NULL;
}
};
vector<struct Node*> g(110);
int n,m,s,t,minT;
void dfs(int u,int reach,int Sbegin)
{
int i,b,e,c,v;
if(u==t)
{
if((reach - Sbegin)<minT)
minT = reach - Sbegin;
return;
}
for(struct Node *p = g[u]->next;p!=NULL;p=p->next)
{
v = p->v;
b = p->b;
e = p->e;
c = p->c;
int uReach = reach;
if(u==s)
{
if(b > 0)
{
Sbegin = b;
uReach = b;
}
}
int begin = uReach>b?uReach:b;
if((e-begin)>=c && (begin+c-Sbegin)<minT)
{
dfs(v,begin+c,Sbegin);
}
}
}
int main()
{
int i,u,v,b,e,c;
cin>>n>>m>>s>>t;
for(i=0;i<g.size();i++)
{
g[i] = new struct Node;
}
for(i=1;i<=m;i++)
{
cin>>u>>v>>b>>e>>c;
struct Node *p;
struct Node *temp = new struct Node;
temp->v = v;
temp->b = b;
temp->e = e;
temp->c = c;
for(p = g[u];p->next!=NULL;p=p->next);
p->next = temp;
temp = new struct Node;
temp->v = u;
temp->b = b;
temp->e = e;
temp->c = c;
for(p = g[v];p->next!=NULL;p=p->next);
p->next = temp;
}
minT = INF;
dfs(s,0,0);
if(minT<INF)
cout<<minT<<endl;
else
cout<<"Impossible"<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator