подскажите я пытаюсь решить задачу http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=193&chapterid=1967#1 с помощью алгоритма дейкстры, но на втором тесте выходит ошибка не могу найти где уже все перепробовал
| Код |
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define fip(a) for(int i=0;i<(a);i++)
#define fjp(b) for(int j=0;j<(b);j++)
using namespace std;
class task{
private:
struct vertex{
int v;
int l;
int c;
vertex(const int &v,const int &l,const int &c){
this->v=v;
this->l=l;
this->c=c;
}
vertex(){
}
};
struct final{
int l;
int c;
};
typedef vector<vertex> vv;
typedef vector<final> vf;
vv *g;
vf results;
int N,M;
bool stop;
void read_data_from_file(){
const int TRUCT_WEIGHT=3000000;
int a,b,c,d;
FILE *file=fopen("input.txt","r");
fscanf(file,"%d %d",&N,&M);
g=new vv[N];
fip(M){
fscanf(file,"%d %d %d %d",&a,&b,&c,&d);
d-=TRUCT_WEIGHT; d/=100;
if((d>0)&&(c<=1440)) {
a--;b--;
g[a].push_back(vertex(b,c,d));
g[b].push_back(vertex(a,c,d));
}
}
fclose(file);
stop=false;
}
void deikstra(){
const int INF =10000000;
final *d=new final[N];
fip(N){
d[i].l=INF;
d[i].c=INF;
}
vector<int> p(N);
d[0].l=0;
vector<bool> u(N,false);
fip(N){
int v=-1;
fjp(N) {
if(!u[j]&&(v==-1||d[j].l<d[v].l))
{
v=j;
}
}
if(d[v].l==INF) break;
u[v]=true;
fjp(g[v].size()){
int to=g[v][j].v,
len=g[v][j].l,
cap=g[v][j].c;
if(len>-1)
if(d[v].l+len<d[to].l){
d[to].l=d[v].l+len;
p[to]=v;
if(cap<d[to].c) d[to].c=cap;
//printf("%d or %d real %d\n",d[v].c,d[to].c,cap);
}
}
}
// printf("well done %d from F\n",d[N-1]);
if(d[N-1].l!=INF){
results.push_back(d[N-1]);
vector<int> path;
for(int v=N-1;v!=0;v=p[v])
path.push_back(v);
path.push_back(0);
if(path.size()>0){
int end=path[0];
int last=path[1];
fip(g[last].size()){
if(g[last][i].v==end)
g[last][i].l=-1;
//g[last].erase(g[last].begin()+i);
}
}
else stop=true;
//reverse(path.begin(),path.end());
// fip(path.size()) printf("%d ",path[i]);
} else stop=true;
}
void q_sort(vf &res,const int &low,const int &high){
int i=low;
int j=high;
int x=res[(low+high)/2].c;
do{
while(res[i].c>x) ++i;
while(res[j].c<x) --j;
if(i<=j){
final temp=res[i];
res[i]=res[j];
res[j]=temp;
i++; j--;
}
} while(i<=j);
if(low<j) q_sort(res,low,j);
if(high>i) q_sort(res,i,high);
}
public:
void decide_task(){
read_data_from_file();
bool no_answer=true;
int max=0;
while(!stop)
deikstra();
const int size=results.size();
//if(size>1)
// q_sort(results,0,size-1);
fip(size){
if((results[i].c>max)&&(results[i].l<=1440))
max=results[i].c;
}
/* fip(size){
if(results[i].l<=1400){
printf("%d",results[i].c);
no_answer=false;
break;
}
}
if(no_answer) printf("0");*/
printf("%d",max);
/* fip(results.size())
printf("%d %d\n",results[i].l,results[i].c);
printf("rs %d",results.size());*/
}
};
int main(){
task t;
t.decide_task();
/*vector<int> d;
fip(4) d.push_back(i);
d.erase(d.begin()+1);
fip(d.size()) printf("%d ",d[i]);*/
return 0;
}
|
|