Submission #8066212
Source Code Expand
#include <cstdio>
#include <vector>
#include <set>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
struct edge
{
int to;
int cost;
};
int n, m;
std::vector<edge> edges[100];
std::set<std::pair<int, int>> path;
void dijkstra(int s)
{
int prev[100];
std::fill(prev, prev + n, -1);
int dist[100];
std::fill(dist, dist + n, 1e9);
dist[s] = 0;
using pair = std::pair<int, int>;
std::priority_queue<pair, std::vector<pair>, std::greater<pair>> q;
q.emplace(pair{0, s});
while (!q.empty())
{
auto p = q.top(); q.pop();
int v = p.second;
if (dist[v] < p.first) continue;
for (auto e : edges[v])
{
if (dist[e.to] > dist[v] + e.cost)
{
dist[e.to] = dist[v] + e.cost;
q.emplace(pair{dist[e.to], e.to});
prev[e.to] = v;
}
}
}
for (int t = s + 1; t != -1 && t != n; t = prev[t])
{
if (prev[t] == -1) break;
path.insert(pair{std::min(t, prev[t]), std::max(t, prev[t])});
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
--a, --b;
edges[a].emplace_back(edge{b, c});
edges[b].emplace_back(edge{a, c});
}
for (int i = 0; i < n; ++i)
{
dijkstra(i);
}
printf("%d\n", m - path.size());
return 0;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:66:33: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::set<std::pair<int, int> >::size_type {aka long unsigned int}’ [-Wformat=]
printf("%d\n", m - path.size());
^
./Main.cpp:53:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:57:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
WA |
1 ms |
256 KB |
subtask_1_03.txt |
WA |
1 ms |
256 KB |
subtask_1_04.txt |
AC |
1 ms |
256 KB |
subtask_1_05.txt |
WA |
3 ms |
256 KB |
subtask_1_06.txt |
WA |
1 ms |
256 KB |
subtask_1_07.txt |
WA |
1 ms |
256 KB |
subtask_1_08.txt |
WA |
1 ms |
256 KB |
subtask_1_09.txt |
WA |
1 ms |
256 KB |
subtask_1_10.txt |
WA |
2 ms |
256 KB |
subtask_1_11.txt |
WA |
1 ms |
256 KB |
subtask_1_12.txt |
WA |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
2 ms |
256 KB |
subtask_1_14.txt |
WA |
2 ms |
256 KB |
subtask_1_15.txt |
AC |
2 ms |
256 KB |
subtask_1_16.txt |
WA |
1 ms |
256 KB |
subtask_1_17.txt |
WA |
1 ms |
256 KB |
subtask_1_18.txt |
WA |
2 ms |
256 KB |
subtask_1_19.txt |
WA |
2 ms |
256 KB |
subtask_1_20.txt |
WA |
1 ms |
256 KB |
subtask_1_21.txt |
WA |
1 ms |
256 KB |
subtask_1_22.txt |
WA |
1 ms |
256 KB |
subtask_1_23.txt |
WA |
2 ms |
256 KB |
subtask_1_24.txt |
WA |
3 ms |
256 KB |
subtask_1_25.txt |
WA |
2 ms |
256 KB |
subtask_1_26.txt |
WA |
2 ms |
256 KB |
subtask_1_27.txt |
WA |
4 ms |
256 KB |
subtask_1_28.txt |
AC |
2 ms |
256 KB |