이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int long long
using namespace std;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
const int maxn=1e5+33;
const int N=1e5;
const int mod=1e9+7;
const long long INF=1e18;
int n,k,m,imp[maxn],vis[maxn][32];
long long dp[maxn][32],f[maxn][6];
vector<int> adj[maxn];
struct edge
{
int u,v,w;
}e[2*maxn];
struct ele
{
int des,mask;
long long dis;
};
bool operator <(ele a,ele b)
{
return a.dis>b.dis;
}
priority_queue<ele> pq;
void predijkstra()
{
for(int i=1;i<=n;i++)
{
if(imp[i])
{
pq.push({i,imp[i]-1,0});
}
}
while(!pq.empty())
{
int des=pq.top().des;
long long dis=pq.top().dis;
int mask=pq.top().mask;
pq.pop();
if(vis[des][mask]) continue;
f[des][mask]=dis;
vis[des][mask]=1;
for(int i:adj[des])
{
int des1=e[i].u+e[i].v-des;
if(!vis[des1][mask])
pq.push({des1,mask,dis+e[i].w});
}
}
}
void dijkstra()
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<(1<<k);j++) vis[i][j]=0;
if(imp[i])
{
pq.push({i,0,0});
}
}
while(!pq.empty())
{
int des=pq.top().des;
long long dis=pq.top().dis;
int mask=pq.top().mask;
pq.pop();
if(vis[des][mask]) continue;
dp[des][mask]=dis;
vis[des][mask]=1;
for(int i:adj[des])
{
int des1=e[i].u+e[i].v-des;
if(!vis[des1][mask])
pq.push({des1,mask,dis+e[i].w});
}
for(int i=0;i<k;i++)
{
if(((1<<i)|mask)!=mask)
{
if(!vis[des][mask^(1<<i)])
{
pq.push({des,(1<<i)^mask,dp[des][mask]+f[des][i]});
}
}
}
}
}
signed main()
{
if (fopen(taskname".INP","r"))
{
freopen(taskname".INP","r",stdin);
freopen(taskname".OUT","w",stdout);
}
Faster
cin>>n>>k>>m;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
imp[x]=i;
}
for(int i=1;i<=m;i++)
{
cin>>e[i].u>>e[i].v>>e[i].w;
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
}
predijkstra();
dijkstra();
long long ans=INF;
for(int i=1;i<=n;i++)
{
if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
// for(int j=0;j<k;j++)
// {
// cout<<f[i][j]<<" ";
// }
// cout<<"\n";
}
cout<<ans;
}
컴파일 시 표준 에러 (stderr) 메시지
cities.cpp: In function 'int main()':
cities.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen(taskname".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(taskname".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |