이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #pragma GCC optimize("O3")
#include <cstdio>
#include <queue>
using namespace std;
int main(){
int n, k, m;
scanf("%d%d%d", &n, &k, &m);
vector <vector <int> > adjLis1(n);
vector <vector <long long> > disLis1(n);
vector <int> important(k);
for(int& i:important){
scanf("%d", &i);
i--;
}
while(k<4){
important.push_back(important.back());
k++;
}
for(int i = m;i --;){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--;b--;
adjLis1[a].push_back(b);
disLis1[a].push_back(c);
adjLis1[b].push_back(a);
disLis1[b].push_back(c);
}
vector <vector <long long> > multisource(k, vector <long long> (n, 1e14));
for(int i = 0;i < k;i ++){
vector <long long>& dist=multisource[i];
int source=important[i];
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis1[x].size();i ++){
int y=adjLis1[x][i];
long long dd=disLis1[x][i];
if(dist[y]>d+dd){
dist[y]=d+dd;
dijkstra.push(make_pair(dist[y], y));
}
}
}
}
if(k==5){
vector <vector <long long> > two;
int x, y;
//0 1
x=0, y=1;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//0 2
x=0, y=2;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//0 3
x=0, y=3;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//0 4
x=0, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//1 2
x=1, y=2;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//1 3
x=1, y=3;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//1 4
x=1, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//2 3
x=2, y=3;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//2 4
x=2, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//3 4
x=3, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
long long best=1e14;
for(int i = 0;i < n;i ++){
best=min(best, two[0][i]+two[7][i]+multisource[4][i]);
best=min(best, two[1][i]+two[5][i]+multisource[4][i]);
best=min(best, two[2][i]+two[4][i]+multisource[4][i]);
best=min(best, two[0][i]+two[8][i]+multisource[3][i]);
best=min(best, two[1][i]+two[6][i]+multisource[3][i]);
best=min(best, two[3][i]+two[4][i]+multisource[3][i]);
best=min(best, two[0][i]+two[9][i]+multisource[2][i]);
best=min(best, two[2][i]+two[6][i]+multisource[2][i]);
best=min(best, two[3][i]+two[5][i]+multisource[2][i]);
best=min(best, two[1][i]+two[9][i]+multisource[1][i]);
best=min(best, two[2][i]+two[8][i]+multisource[1][i]);
best=min(best, two[3][i]+two[7][i]+multisource[1][i]);
best=min(best, two[4][i]+two[9][i]+multisource[0][i]);
best=min(best, two[5][i]+two[8][i]+multisource[0][i]);
best=min(best, two[6][i]+two[7][i]+multisource[0][i]);
}
printf("%lld\n", best);
}
}
컴파일 시 표준 에러 (stderr) 메시지
cities.cpp: In function 'int main()':
cities.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis1[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:180:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:214:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:248:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:282:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:316:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:350:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:384:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &i);
~~~~~^~~~~~~~~~
cities.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |