나는이 코드를 uri 온라인 판사에게 넘겨 줬지만 내 오류가 어디에 있는지, 나는 모든 시험을했는지 모른다.최단 경로 - URI 온라인 판사 1640
링크 문제는 이것이다 : https://www.urionlinejudge.com.br/repository/UOJ_1640_en.html
문제의 설명은 다음과 같습니다
는트랜스 회사는 종종 다른 도시로 한 도시에서 물품을 인도 할 필요가있다. 운송 회사는 운전 기사가이 체인 호텔에 무료로 숙박 할 수있게 해주는 호텔 체인과 특별 계약을 맺었습니다. 운전자는 하루에 최대 10 시간 운전할 수 있습니다. 운송 회사는 출발 도시에서 목적지 도시까지의 경로를 찾아 드라이버가 항상 호텔 체인 호텔 중 한 곳에서 밤을 보낼 수 있도록하고 호텔에서 호텔까지 최대 10 시간 운전해야합니다 다음 호텔 (또는 목적지). 물론 물품 배달에 필요한 일수도 최소화해야합니다. 입력
입력 파일에는 여러 가지 테스트 케이스가 있습니다. 각 테스트 케이스는 정수 n (2 ≤ n ≤ 10000)을 포함하는 라인부터 시작하여 경로를 계획 할 때 고려해야 할 도시의 수입니다. 단순화를 위해 도시는 1에서 n까지 번호가 매겨집니다. 여기서 1은 시작 도시이고 n은 대상 도시입니다. 다음 줄에는 호텔 체인 호텔이 위치한 도시의 번호를 나타내는 숫자 h, 숫자 c1, c2, ..., ch가 뒤에 오는 정수 h가 포함됩니다. 0 ≤ h ≤ min (n, 100)이라고 가정 할 수 있습니다. 각 테스트 케이스의 세 번째 행에는 경로를 계획 할 때 고려해야 할 도로 수 m (1 ≤ m ≤ 105)의 정수가 포함됩니다. 다음의 m 줄은 도로를 설명합니다. 각 도로는 3 개의 정수 a, b, t (1 ≤ a, b ≤ n 및 1 ≤ t ≤ 600)를 포함하는 선으로 표시되며, 여기서 a, b는 도로로 연결된 두 도시이고 t는 운전자가 도로 끝에서 다른 끝까지 운전하는데 필요한 분. 입력은 n = 0으로 종료됩니다. 출력
각 테스트 케이스에 대해 운송 회사가 도시 1에서 도시 n으로 배달하기 위해 예약해야하는 최소 호텔 수를 포함하는 한 줄을 인쇄하십시오. 운전자가 하루에 최대 10 시간 운전해야하는 경로를 찾을 수 없다면 대신 -1을 인쇄하십시오.
나의 시도 솔루션은 내 GitHub의에 : 어떤 도움 https://github.com/h31nr1ch/uri/blob/master/1640.cpp#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <limits> // for numeric_limits
#include <set>
#include <utility> // for pair
#include <algorithm>
#include <iterator>
using namespace std;
typedef long long int vertex_t;
typedef double weight_t;
const weight_t max_weight = numeric_limits<double>::infinity();
struct neighbor {
vertex_t target;
weight_t weight;
weight_t current;
bool hotel;
neighbor(vertex_t arg_target, weight_t arg_weight,weight_t arg_current,bool arg_hotel):target(arg_target), weight(arg_weight),current(arg_current),hotel(arg_hotel){ }
};
typedef vector<vector<neighbor> > adjacency_list_t;
void DijkstraComputePaths(vertex_t source,adjacency_list_t &adjacency_list, vector<weight_t> &min_distance, vector<vertex_t> &previous,vector<vertex_t> &hoteis,vector<vertex_t> &weights,vector<bool> &tHotel){
int n = adjacency_list.size();
min_distance.clear();
min_distance.resize(n, max_weight);
min_distance[source] = 0;
previous.clear();
previous.resize(n, -1);
weights.clear();
weights.resize(n,0);
tHotel.clear();
tHotel.resize(n,false);
set<pair<weight_t, vertex_t> > vertex_queue;
vertex_queue.insert(make_pair(min_distance[source], source));
while (!vertex_queue.empty()){
weight_t dist = vertex_queue.begin()->first;
vertex_t u = vertex_queue.begin()->second;
vertex_queue.erase(vertex_queue.begin());
vector<neighbor> &neighbors = adjacency_list[u];
for (vector<neighbor>::iterator neighbor_iter = neighbors.begin(); neighbor_iter != neighbors.end(); neighbor_iter++){
vertex_t v = neighbor_iter->target;
weight_t weight = neighbor_iter->weight;
weight_t current= neighbor_iter->current;
weight_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v]) {
bool l=true;
bool ho=false;//Variavel criada para falar se dormiu no hotel ou nao
//if(distance_through_u>600){
if(weight+weights[u]>600){
//Procurando por um hotel
if(hoteis.size()==0)
l=false;
for(vector<vertex_t>::iterator it=hoteis.begin();it!=hoteis.end();it++){
if(*it==u){
l=true;
ho=true;
break;
}
else{
l=false;
}
}
}
if(l){
if(ho){
tHotel[v]=true;
weights[v]=weight;
//cout<<"O nó u= "<<u<<" e nó v= "<<v<<" precisaram de hotel! Entao o peso é: "<<weights[v]<<endl;
}
else{
tHotel[v]=false;
weights[v]=distance_through_u;
//cout<<"O nó u= "<<u<<" e nó v= "<<v<<" NÃO precisaram de hotel! Entao o peso é: "<<weights[v]<<endl;
}
vertex_queue.erase(make_pair(min_distance[v], v));
min_distance[v] = distance_through_u;
previous[v] = u;
vertex_queue.insert(make_pair(min_distance[v], v));
}
}
}
}
}
list<vertex_t> DijkstraGetShortestPathTo(vertex_t vertex, const vector<vertex_t> &previous){
list<vertex_t> path;
for (;vertex != -1; vertex = previous[vertex])
path.push_front(vertex);
return path;
}
int main(){
int n=1,m,x,y,w,v;
while(n!=0){
vector<vertex_t> hoteis;
cin>>n;
adjacency_list_t adjacency_list(n);
if(n==0)
break;
cin>>v;
for(int i=0;i<v;i++){
cin>>x;
hoteis.push_back(x-1);
}
cin>>m;
for(int i=0;i<m;i++){
cin>>x>>y>>w;
adjacency_list[x-1].push_back(neighbor(y-1,w,0,false));
}
vector<weight_t> min_distance;
vector<vertex_t> previous;
vector<vertex_t> weights;
vector<bool> tHotel;
DijkstraComputePaths(0, adjacency_list, min_distance, previous,hoteis,weights,tHotel);
//cout << "Distance from 0 to "<<n-1<<" : " << min_distance[n-1] << endl;
list<vertex_t> path = DijkstraGetShortestPathTo(n-1, previous);
//cout<<"Weights: ";
//copy(min_distance.begin(),min_distance.end(),ostream_iterator<vertex_t>(cout," "));
//cout<<endl;
//cout << "Path : ";
//copy(path.begin(), path.end(), ostream_iterator<vertex_t>(cout, " "));
//cout<<endl;
int total=0;
//for(vector<bool>::iterator it=tHotel.begin();it!=tHotel.end();it++){
// cout<<*it<<" ";
//}
for(list<vertex_t>::iterator it=path.begin();it!=path.end();it++){
if(tHotel[*it]==1)
total++;
}
//cout<<endl;
if(min_distance[n-1]==max_weight){
cout<<"-1\n";
}
else{
cout<<total<<endl;
}
}
return 0;
}
감사합니다.