이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC tarGet ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC tarGet("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = 1e5;
const int maxN = 2e5 + 1;
const int mod = 1e9 + 7;
const int block_size = 700;
const ll infty = 1e18;
void InputFile()
{
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
freopen("test.out","r",stdin);
}
struct Tpq
{
int ver,pre;
int state;
ll val;
};
struct functer
{
bool operator()(Tpq a,Tpq b)
{
return a.val > b.val;
}
};
int n,m;
int x[maxN],y[maxN],c[maxN],p[maxN];
vector<int> adj[maxN];
ll dp[1005][1005][2];
int cnt[maxN];
void Read()
{
cin >> n >> m;
for(int i = 1;i <= m;i++)
{
cin >> x[i] >> y[i] >> c[i] >> p[i];
adj[x[i]].push_back(i);
adj[y[i]].push_back(i);
}
}
void Dijkstra()
{
for(int i = 1;i <= n;i++)
{
for(int j = 0;j <= n;j++)
{
dp[i][j][0] = infty;
dp[i][j][1] = infty;
}
}
priority_queue<Tpq,vector<Tpq>,functer> q;
dp[1][0][0] = 0;
q.push({1,0,0,0});
do
{
Tpq pick = q.top();
q.pop();
int u = pick.ver;
int pre = pick.pre;
int state = pick.state;
if(dp[u][pre][state] != pick.val) continue;
for(int i : adj[u])
{
int v = x[i] + y[i] - u;
if(state && v == pre) continue;
cnt[c[i]]++;
}
for(int i : adj[u])
{
int v = x[i] + y[i] - u;
if(state && v == pre) continue;
ll su = p[i] * (cnt[c[i]] > 1);
int nxt_state = (su > 0);
if(dp[v][u][nxt_state] > dp[u][pre][state] + su)
{
dp[v][u][nxt_state] = dp[u][pre][state] + su;
q.push({v,u,nxt_state,dp[v][u][nxt_state]});
}
}
for(int i : adj[u])
{
cnt[c[i]] = 0;
}
}
while(!q.empty());
}
void Solve()
{
Dijkstra();
ll res = infty;
for(int i = 0;i <= n;i++)
{
res = min(res,dp[n][i][0]);
res = min(res,dp[n][i][1]);
}
if(res >= infty) res = -1;
cout << res;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//InputFile();
//int sub_type;
//cin >> sub_type;
//Sieve();
int test;
//cin >> test;
test = 1;
while(test--)
//for(int prc = 1; prc <= test; prc++)
{
Read();
Solve();
//Debug();
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void InputFile()':
Main.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen("test.out","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |