# 2345_Cost_and_Time_TA

Kotori
c_cpp
16 days ago
3.1 kB
0
Indexable
Never
```//#pragma wanring (disable:4996)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
#include<set>

using namespace std;

#define maxN 105
#define inf 99999999
int n, k;

class State {
public:
int cost, time;

State(int c, int t)
{
cost = c;
time = t;
}
};

class Point {
public:
int city, cost, time;

Point(int c, int co, int t)
{
city = c;
cost = co;
time = t;
}

bool operator< (const Point& otherPoint) const {
return time > otherPoint.time;
}
};

int cnt[maxN];

int time_to_dest[maxN][maxN];

void init(int N, int K, int sCity[], int eCity[], int mCost[], int mTime[])
{
n = N;
for (int i = 0; i < N; i++)
{
cnt[i] = 0;
for (int j = 0; j < N; j++)
{
time_to_dest[i][j] = inf;
}
}

for (int i = 0; i < K; i++)
{
}

}

void add(int sCity, int eCity, int mCost, int mTime)
{
{
}
else
{
}
}

int cost(int M, int sCity, int eCity)
{
Point res(eCity, inf, inf);

for (int i = 0; i < maxN; i++)
{
time_to_dest[sCity][i] = inf;
}

priority_queue<Point> pq;

time_to_dest[sCity][sCity] = 0;

pq.push({ sCity, 0, 0 });

//cout << "sCity = " << sCity << endl;

while (!pq.empty())
{
Point cur_p = pq.top(); pq.pop();

//cout << "cur_p.city = " << cur_p.city << endl;
if (cur_p.city == eCity)
{
if (res.time > time_to_dest[sCity][eCity])
{
res.time = time_to_dest[sCity][eCity];
}
}
for (int i = 0; i < cnt[cur_p.city]; i++)
{

for (int j = 0; j < Road[cur_p.city][new_city].size(); j++)
{

if (cur_p.cost + cost <= M /*&& time_to_dest[sCity][cur_p.city] + time < time_to_dest[sCity][new_city]*/)
{
time_to_dest[sCity][new_city] = cur_p.time + time;
pq.push({ new_city, cur_p.cost + cost, cur_p.time + time });
}
}

}
}

//cout << time_to_dest[sCity][eCity] << endl;
//return time_to_dest[sCity][eCity] == inf ? -1 : time_to_dest[sCity][eCity];
return res.time == inf ? -1 : res.time;
}

int main()
{
//freopen("input.txt", "r", stdin);
int sCity[3] = { 0, 1, 3 };
int eCity[3] = { 1, 3, 4 };
int mCost[3] = { 80, 70, 20 };
int mTime[3] = { 50, 20, 10 };

init(5, 3, sCity, eCity, mCost, mTime);
int res = cost(200, 1, 2);
cout << res << endl;
res = cost(200, 0, 4);
cout << res << endl;