Problem:


Score : 400 points

Problem Statement

You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.

The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

A connected graph is a graph where there is a path between every pair of different vertices.

Find the number of the edges that are not contained in any shortest path between any pair of different vertices.  

Constraints

2≤N≤100 

N-1≤M≤min(N(N-1)/2,1000) 

1≤a_i,b_i≤N 

1≤c_i≤1000

c_i is an integer.

The given graph contains neither self-loops nor double edges.

The given graph is connected.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

Sample Output 1

1

In the given graph, the shortest paths between all pairs of different vertices are as follows:

The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2, with the length of 1.

The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3, with the length of 1.

The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1, with the length of 1.

The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3, with the length of 2.

The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1, with the length of 1.

The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2, with the length of 2.

Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3, hence the output should be 1.

Sample Input 2

3 2
1 2 1
2 3 1

Sample Output 2

0

Every edge is contained in some shortest path between some pair of different vertices.



Sample input:
3 3
1 2 1
1 3 1
2 3 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
INF=100000000000


def floyd_warshall(dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (dist[i][j] > dist[i][k]+dist[k][j]):
                    dist[i][j] = dist[i][k]+dist[k][j]
                    dist[j][i] = dist[i][k]+dist[k][j]

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

for i in range(n):
    dist[i][i] = 0

floyd_warshall(dist)

#print(dist)
count = 0
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
INF=100000000000


def floyd_warshall(dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (dist[i][j] > dist[i][k]+dist[k][j]):
                    dist[i][j] = dist[i][k]+dist[k][j]
                    dist[j][i] = dist[i][k]+dist[k][j]

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci-1]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

for i in range(n):
    dist[i][i] = 0

floyd_warshall(dist)

#print(dist)
count = 0
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
INF=100000000000


def floyd_warshall(dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (dist[i][j] > dist[i][k]+dist[k][j]):
                    dist[i][j] = dist[i][k]+dist[k][j]
                    dist[j][i] = dist[i][k]+dist[k][j]

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci-1]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

for i in range(n):
    dist[i][i] = 0

floyd_warshall(dist)

#print(dist)
count = 0
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1
            break


    if flag > 0:
        count+=1
    else:
        continue

print(count)

Submission status: Wrong Answer

Solution code:
INF=100000000000


def dijkstra(s,t,adj,dist):
    to_visit = [s]
    visited=[False]*n
    d=[INF]*n
    d[s] = 0
    while len(to_visit) > 0:
        w = to_visit[0]
        for node in to_visit:
            if d[w] > d[node]:
                w = node

        if w == t:
            return d[w]
        to_visit.remove(w)
        visited[w]=True
        for node in adj[w]:
            if visited[node] == True:
                continue
            else:
                new_dist = d[w]+dist[w][node]
                if new_dist < d[node]:
                    d[node] = new_dist
                    to_visit.append(node)

    return INF




n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
adj=[[] for i in range(n)]
D=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci-1]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci
    adj[ai-1].append(bi-1)
    adj[bi-1].append(ai-1)

for i in range(n):
    for j in range(n):
        D[i][j] = dijkstra(i,j,adj,dist)

#print(D)
count = 0
for edge in edges:
    ai,bi,ci=edge[0],edge[1],edge[2]
    flag = 0
    for s in range(n):
        if D[s][ai]+ci == D[s][bi]:
            flag+=1
            break

    if flag > 0:
        count+=1
    else:
        continue

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
graph = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = a

edge = set()
graph2 = graph.copy()
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph2[i][k] + graph2[k][j] < graph2[i][j]:
                graph2[i][j] = min(graph2[i][j], graph2[i][k] + graph2[k][j])

for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph2[i][j]:
                edge.add(tuple([i, j]))


print(int(M - ((len(edge)-N) / N)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n,m=map(int,input().split())
v=[[0 for i in range(n)] for i in range(n)]
used=[[0 for i in range(n)] for i in range(n)]
cost_table=[[99999999 for i in range(n)] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    v[a-1][b-1]=1
    v[b-1][a-1]=1
    cost_table[a-1][b-1]=c
    cost_table[b-1][a-1]=c

init_cost_table=[]
for i in range(n):
    init_cost_table.append(cost_table[i][:])

for i in range(n):
    for j in range(n):
        for k in range(n):
            if cost_table[i][k]>cost_table[i][j]+cost_table[j][k]:
                cost_table[i][k]=cost_table[i][j]+cost_table[j][k]
    cost_table[i][i]=0

memo={}
def Path(start,goal):
    cur = start;
    while cur != goal:
        if (cur,goal) in memo:
            break
        else:
            memo[(cur,goal)]=1
        for i in range(n):
            if (i != cur and init_cost_table[cur][i] + cost_table[i][goal] == cost_table[cur][goal]):
                used[cur][i]=1
                used[i][cur]=1
                cur = i
                break
for i in range(n):
    for j in range(n):
        Path(i,j)
ans=0
for i in range(n):
    ans+=sum(v[i])
for i in range(n):
    ans-=sum(used[i])
if ans//2 <0:
    while 1:
        pass
print(ans//2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n,m=map(int,input().split())
v=[[0 for i in range(n)] for i in range(n)]
used=[[0 for i in range(n)] for i in range(n)]
cost_table=[[99999999 for i in range(n)] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    v[a-1][b-1]=1
    v[b-1][a-1]=1
    cost_table[a-1][b-1]=c
    cost_table[b-1][a-1]=c

init_cost_table=[]
for i in range(n):
    init_cost_table.append(cost_table[i][:])

for i in range(n):
    for j in range(n):
        for k in range(n):
            if cost_table[i][k]>cost_table[i][j]+cost_table[j][k]:
                cost_table[i][k]=cost_table[i][j]+cost_table[j][k]
    cost_table[i][i]=0

memo={}
def Path(start,goal):
    cur = start;
    while cur != goal:
        if (cur,goal) in memo:
            break
        else:
            memo[(cur,goal)]=1
        for i in range(n):
            if (i != cur and init_cost_table[cur][i] + cost_table[i][goal] == cost_table[cur][goal]):
                used[cur][i]=1
                used[i][cur]=1
                cur = i
                break
for i in range(n):
    for j in range(n):
        Path(i,j)
ans=0
for i in range(n):
    ans+=sum(v[i])
for i in range(n):
    ans-=sum(used[i])
print(ans//2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n,m=map(int,input().split())
v=[[0 for i in range(n)] for i in range(n)]
used=[[0 for i in range(n)] for i in range(n)]
cost_table=[[99999999 for i in range(n)] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    v[a-1][b-1]=1
    v[b-1][a-1]=1
    cost_table[a-1][b-1]=c
    cost_table[b-1][a-1]=c

init_cost_table=[]
for i in range(n):
    init_cost_table.append(cost_table[i][:])

for i in range(n):
    for j in range(n):
        for k in range(n):
            if cost_table[i][k]>cost_table[i][j]+cost_table[j][k]:
                cost_table[i][k]=cost_table[i][j]+cost_table[j][k]
    cost_table[i][i]=0

memo={}
def Path(start,goal):
    cur = start;
    while cur != goal:
        if (cur,goal) in memo:
            break
        else:
            memo[(cur,goal)]=1
        for i in range(n):
            if (i != cur and init_cost_table[cur][i] + cost_table[i][goal] == cost_table[cur][goal]):
                used[cur][i]=1
                used[i][cur]=1
                cur = i
                break
for i in range(n):
    for j in range(i+1,n):
        Path(i,j)
ans=0
for i in range(n):
    ans+=sum(v[i])
for i in range(n):
    ans-=sum(used[i])
print(ans//2)

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  import copy
  d=copy.deepcopy(edges)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

inf=float("inf")
N,M=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(M)]
A=[[inf for j in range(N)] for i in range(N)]#最短距離map
for i in range(N):
  A[i][i]=0
for i in range(M):
  A[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
  A[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
Ans=Warshall_Floyd(A,N)
ans=0
for j in range(M):
  B=[[inf for j in range(N)] for i in range(N)]#最短距離map
  for i in range(N):
    B[i][i]=0
  for i in range(M):
    if i!=j:
      B[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
      B[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
  Bns=Warshall_Floyd(B,N)
  if Bns==Ans: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  import copy
  d=copy.deepcopy(edges)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

inf=float("inf")
N,M=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(M)]
A=[[inf for j in range(N)] for i in range(N)]#最短距離map
for i in range(N):
  A[i][i]=0
for i in range(M):
  A[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
  A[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
Ans=Warshall_Floyd(A,N)
ans=0
for j in range(M):
  u=abc[j][0]-1
  v=abc[j][0]-1
  for s in range(N):
    if Ans[s][u]+abc[j][2]==Ans[s][v]:
      ans+=1
      break
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(M)]

E = defaultdict(list)
for a, b, c in X:
    E[a].append((b, c))
    E[b].append((a, c))

def dijkstra(E, s):
    visited = set()
    prev = {}
    hq = []
    heapq.heappush(hq, (0, s, -1))
    while hq:
        cost, a, p = heapq.heappop(hq)
        if a in visited:
            continue
        visited.add(a)
        prev[a] = p
        for b, c in E[a]:
            if b in visited:
                continue
            heapq.heappush(hq, (cost + c, b, a))
    return prev

minpath = set()
for s in range(1, N+1):
    prev = dijkstra(E, s)
    for k in prev:
        if prev[k] == -1:
            continue
        minpath.add((k, prev[k]))
        minpath.add((prev[k], k))
print M - len(minpath) / 2

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(M)]

E = defaultdict(list)
for a, b, c in X:
    E[a].append((b, c))
    E[b].append((a, c))

def dijkstra(E, s):
    visited = set()
    prev = {}
    hq = []
    heapq.heappush(hq, (0, s, -1))
    while hq:
        cost, a, p = heapq.heappop(hq)
        visited.add(a)
        prev[a] = p
        for b, c in E[a]:
            if b in visited:
                continue
            heapq.heappush(hq, (cost + c, b, a))
    return prev

minpath = set()
for s in range(1, N+1):
    prev = dijkstra(E, s)
    for k in prev:
        if prev[k] == -1:
            continue
        minpath.add((k, prev[k]))
        minpath.add((prev[k], k))
print M - len(minpath) / 2

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(M)]

E = defaultdict(list)
for a, b, c in X:
    E[a].append((b, c))
    E[b].append((b, c))

def dijkstra(E, s):
    visited = set()
    prev = {}
    hq = []
    heapq.heappush(hq, (0, s, -1))
    while hq:
        cost, a, p = heapq.heappop(hq)
        visited.add(a)
        prev[a] = p
        for b, c in E[a]:
            if b in visited:
                continue
            heapq.heappush(hq, (cost + c, b, a))
    return prev

minpath = set()
for s in range(1, N+1):
    prev = dijkstra(E, s)
    for k in prev:
        if prev[k] == -1:
            continue
        minpath.add((k, prev[k]))
        minpath.add((prev[k], k))
print M - len(minpath) / 2

Submission status: Wrong Answer

Solution code:
N,M = map(int, raw_input().split())
EDGES = {}
d = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  EDGES[(min(a,b),max(a,b))] = c
  d[a-1][b-1] = c
  d[b-1][a-1] = c

for k in range(N):
  for i in range(N):
    for j in range(N):
      if(d[i][j] > d[i][k] + d[k][j]):
        d[i][j] = d[i][k] + d[k][j]

unused = 0
for j in range(N):
  for i in range(j):
    if((i,j) in EDGES and EDGES[(i,j)] != d[i][j]):
      unused += 1
print unused

Submission status: Wrong Answer

Solution code:
N,M = map(int, raw_input().split())
EDGES = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  EDGES[a-1][b-1] = c
  EDGES[b-1][a-1] = c
notused = 0
for i in range(N):
  for j in range(i):
    edge = EDGES[i][j]
    if edge == 0:
      continue
    for k in range(N):
      if(k == i or k == j or EDGES[i][k] == 0 or EDGES[k][j] == 0):
        continue
      if edge > EDGES[i][k] + EDGES[k][j]:
        notused += 1
print notused

Submission status: Wrong Answer

Solution code:
N,M = map(int, raw_input().split())
EDGES = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  EDGES[a-1][b-1] = c
  EDGES[b-1][a-1] = c
notused = 0
for i in range(N):
  for j in range(i):
    edge = EDGES[i][j]
    for k in range(N):
      if(k == i or k == j):
        continue
      if edge > EDGES[i][k] + EDGES[k][j]:
        notused += 1
print notused

Submission status: Wrong Answer

Solution code:
N,M = map(int, raw_input().split())
EDGES = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  EDGES[a-1][b-1] = c
  EDGES[b-1][a-1] = c
notused = 0
for i in range(N):
  for j in range(i):
    edge = EDGES[i][j]
    for k in range(N):
      if edge > EDGES[i][k] + EDGES[k][j]:
        notused += 1
print notused

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 10**10
N, M = map(int, raw_input().split())
G = [map(int, raw_input().split()) for i in range(M)]
d = np.full((N+1, N+1), INF)
for i in range(N+1):
    d[i,i] = 0
for u, v, c in G:
    d[u, v] = d[v, u] = c
for s in range(N+1):
    for t in range(N+1):
        for u in range(N+1):
            d[s, t] = d[t, s] = min(d[s, t], d[s, u] + d[u, t])
ans = 0
for u, v, c in G:
    if c > d[u, v]:
        ans += 1
print ans

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

n, m = map(int, input().split())
links = [set() for _ in range(n)]
link_list = []
for _ in range(m):
    s, t, c = map(int, input().split())
    s, t = s - 1, t - 1
    link_list.append((s, t, c))
    links[s].add((c, t))
    links[t].add((c, s))

result = 0
for s, t, limit in link_list:
    queue = [(0, s)]
    visited = set()
    while queue:
        c, v = heappop(queue)
        if v == t:
            result += 1
            break
        if c >= limit:
            break
        if v in visited:
            continue
        visited.add(v)
        for nc, nv in links[v]:
            if nv in visited:
                continue
            if v == s and nv == t:
                continue
            heappush(queue, (c + nc, nv))
print(result)

Submission status: Wrong Answer

Solution code:
from itertools import product as prod

n, m = [int(x) for x in input().split()]

wait = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(n):
    wait[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    wait[a-1][b-1] = c
    wait[b-1][a-1] = c

dist = [[float("inf") for _ in range(n)] for _ in range(n)]
for k, i, j in prod(range(n), range(n), range(n)):
    dist[i][j] = min(wait[i][j], dist[i][k] + dist[k][j])
    dist[j][i] = min(wait[j][i], dist[j][k] + dist[k][i])

ans = 0
for i, j in prod(range(n), range(n)):
    if dist[i][j] < wait[i][j] and not wait[i][j] == float("inf"):
        ans += 1

print(ans // 2)

Submission status: Wrong Answer

Solution code:
from itertools import product as prod

n, m = [int(x) for x in input().split()]

gr = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    gr[a].append((b, c))
    gr[b].append((a, c))

def dist(i, j, ns, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    if (j, _) in gr[i]:
        tmp_d = _
    ns.add(i)
    routes = [d + dist(n, j, ns) for (n, d) in gr[i] if n not in ns]
    
    return min(routes + [tmp_d])

ans = 0
for i in range(n):
    for (j, d) in gr[i]:
        if dist(i, j, set()) < d:
            ans += 1

print(ans // 2)

Submission status: Wrong Answer

Solution code:
from itertools import product as prod

n, m = [int(x) for x in input().split()]

gr = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    gr[a].append((b, c))
    gr[b].append((a, c))

def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    if (j, _) in gr[i]:
        tmp_d = _
    nds = gr[i].copy()
    gr[i] = []
    routes = [d + dist(n, j) for (n, d) in nds]
    
    return min(routes + [tmp_d])

ans = 0
for i in range(n):
    for (j, d) in gr[i]:
        if dist(i, j) < d:
            ans += 1

print(ans // 2)

Submission status: Wrong Answer

Solution code:
from itertools import product as prod

n, m = [int(x) for x in input().split()]

gr = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    gr[a].append((b, c))
    gr[b].append((a, c))

def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    for (n, d) in gr[i]:
        if n == j:
            tmp_d = d
    gr_cp = [[(n, d) for (n, d) in g if n != i] for g in gr]
    routes = [d + dist(n, j, gr=gr_cp) for (n, d) in gr[i]]

    return min(routes + [tmp_d])

ans = 0
for i, j in prod(range(1, m), range(1,m)):
    for (n, d) in gr[i]:
        if n == j and d > dist(i, j):
            ans += 1
print(ans / 2)

Submission status: Wrong Answer

Solution code:
n,m = input().strip().split(' ')
n,m = [int(n),int(m)]
if m>=n:
	print ((m - (n-1)))
else:
	print (0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline().rstrip("\n")

    while line:
        n, m = line.split()
        n = int(n)
        m = int(m)

        edges = []
        path = [[-1 for i in xrange(n)] for i in xrange(n)]
        distance = [[1001 for i in xrange(n)] for i in xrange(n)]
        for i in xrange(m):
            a, b, c = raw_input().split()
            a = int(a) - 1
            b = int(b) - 1
            c = int(c)
            distance[a][b] = c
            distance[b][a] = c
            edges.append((a,b))

        for k in xrange(n):
            for i in xrange(n):
                for j in xrange(n):
                    candidate = distance[i][k] + distance[k][j]
                    if candidate < distance[i][j]:
                        distance[i][j] = candidate
                        distance[j][i] = candidate
                        path[i][j] = k

        counter = 0
        for (x, y) in edges:
            if path[x][y] != -1:
                counter += 1
        print counter

        line = sys.stdin.readline().rstrip("\n")

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
for _ in xrange(m):
    a,b,c=map(int,raw_input().split())
print m-n+1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline().rstrip("\n")

    while line:
        n, m = line.split()
        n = int(n)
        m = int(m)

        edges = []
        path = [[[] for i in xrange(n)] for i in xrange(n)]
        distance = [[0 for i in xrange(n)] for i in xrange(n)]
        for i in xrange(m):
            a, b, c = raw_input().split()
            a = int(a) - 1
            b = int(b) - 1
            c = int(c)
            distance[a][b] = c
            distance[b][a] = c
            edges.append((a,b))

        for i in xrange(n):
            for j in xrange(n):
                for k in xrange(n):
                    candidate = distance[i][k] + distance[k][j]
                    if candidate < distance[i][j]:
                        distance[i][j] = candidate
                        path[i][j].append(k)

        counter = 0
        for (x, y) in edges:
            if path[x][y]:
                counter += 1
        print counter

        line = sys.stdin.readline().rstrip("\n")

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
inf = 10**10
N, M = map(int, input().split())
g = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	g[a-1][b-1] = c
	g[b-1][a-1] = c
g2 = [[inf if not i else i for i in j] for j in g]
for i in range(N):
	g2[i][i] = 0
ans = 0
for i in range(N):
	for j in range(N):
		if g[i][j]:
			f = 1
		else:
			f = 0
		for k in range(N):
			if f == 1 and g2[i][j] > g2[i][k] + g2[k][j]:
				ans += 1
				f = 0
			g2[i][j] = min(g2[i][j],g2[i][k]+g2[k][j])
			g2[j][i] = min(g2[i][j],g2[i][k]+g2[k][j])
print(ans)

Submission status: Wrong Answer

Solution code:
inf = 10**10
N, M = map(int, input().split())
g = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	g[a-1][b-1] = c
	g[b-1][a-1] = c
g2 = [[inf if not i else i for i in j] for j in g]
for i in range(N):
	g2[i][i] = 0
ans = 0
for i in range(N):
	for j in range(i+1,N):
		if g[i][j]:
			f = 1
		else:
			f = 0
		for k in range(N):
			if f == 1 and g2[i][j] > g2[i][k] + g2[k][j]:
				ans += 1
				f = 0
			g2[i][j] = min(g2[i][j],g2[i][k]+g2[k][j])
			g2[j][i] = min(g2[i][j],g2[i][k]+g2[k][j])
print(ans)

Submission status: Wrong Answer

Solution code:
inf = 10**10
N, M = map(int, input().split())
g = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	g[a-1][b-1] = c
	g[b-1][a-1] = c
g2 = [[inf if not i else i for i in j] for j in g]
for i in range(N):
	g2[i][i] = 0
ans = 0
for i in range(N):
	for j in range(i+1,N):
		if g[i][j]:
			f = 1
		else:
			f = 0
		for k in range(N):
			if f == 1 and g2[i][j] > g2[i][k] + g2[k][j]:
				ans += 1
			g2[i][j] = min(g2[i][j],g2[i][k]+g2[k][j])
			g2[j][i] = min(g2[i][j],g2[i][k]+g2[k][j])
print(ans)

Submission status: Wrong Answer

Solution code:
inf = 10**10
N, M = map(int, input().split())
g = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	g[a-1][b-1] = c
	g[b-1][a-1] = c
g2 = [[inf if not i else i for i in j] for j in g]
for i in range(N):
	g2[i][i] = 0
ans = 0
for i in range(N):
	for j in range(i+1,N):
		if g2[i][j] != inf:
			f = 1
		else:
			f = 0
		for k in range(N):
			if f == 1 and g2[i][j] > g2[i][k] + g2[k][j]:
				ans += 1
			g2[i][j] = min(g2[i][j],g2[i][k]+g2[k][j])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0 for i in range(M)]
B = [0 for i in range(M)]
C = [0 for i in range(M)]
dist = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())
	dist[A[i]-1][B[i]-1] = C[i]
	dist[B[i]-1][A[i]-1] = C[i]

for i in range(N):
	for j in range(N):
		for k in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

count = 0
for i in range(M):
	if dist[A[i]-1][B[i]-1] < C[i]:
		count = count+1

print(count)

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in raw_input().split()]

d = [[1000000000] * n for i in range(n)]

edges = []
for i in range(m):
    a, b, c = [int(x) for x in raw_input().split()]
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    edges.append([a, b, c])

for i in range(n):
    for j in range(n):
        for k in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for a, b, c in edges:
    if d[a][b] < c:
        ans += 1

print ans

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,t in l:
    dp[a-1][b-1] = t
    dp[b-1][a-1] = t
#print(dp)

#最短リスト
for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])

#各辺が何かしらの最短ルートに含まれているか
ans = 0
for a, b, t in l:
    cou = 0
    for j in range(n):
        for k in range(n):
            #jからkの最短ルートにa,bが入ってるいるか
            if dp[j][k] != dp[j][a-1] + t + dp[b-1][k]:
                cou += 1
    if cou==n**2:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                if d[i][j] > d[i][k] + d[k][j]:
                  d[i][j] = d[i][k] + d[k][j]
                  if [i, j] in hen:
                    ll = hen.index([i, j])
                    used[ll] += 1
                  elif [j, i] in hen:
                    ll = hen.index([j, i])
                    used[ll] += 1 
        #print(d)
    return d

##############################
n,m = map(int,input().split()) #n:頂点数　m:辺の数

d = [[float("INF")] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
used = [0] * m
hen = [0] * m
for i in range(m):
    x,y,z = map(int,input().split())
    d[x - 1][y - 1] = z
    d[y - 1][x - 1] = z
    hen[i] = [x - 1, y - 1]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

ans = warshall_floyd(d)
#それぞれの出発地点ごとにmaxをとり、そのmaxが最小の地点に引っ越し
#そのときの所要時間がp
#print(used)
zero = used.count(0)
ans = m - zero
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
edge=[]
d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    edge.append([x,y,z])
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
#print(edge)
count=0
for x,y,z in edge:
    flag=True
    for i in range(n):
        for j in range(n):
            if d[i][j]==d[i][x]+z+d[y][j]:
                #print(i,x,y,j)
                flag=False
    if flag==True:
        count+=1
print(count)

#インデックスで与えられていることに注意
#ソース　https://juppy.hatenablog.com/entry/2018/11/01/蟻本_python_全点対最短経路法（ワーシャルフロイド法

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
path = [[float("inf")]*N for i in range(N)]
ans = [[[float("inf")]]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
    ans[a-1][b-1] = [i]
    ans[b-1][a-1] = [i]
for i in range(N):
    path[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if path[i][k]+path[k][j] < path[i][j]:
                path[i][j] = path[i][k]+path[k][j]
                ans[i][j] = ans[i][k]+ans[k][j]
total = []
for i in range(N):
    for j in range(N):
        total = ans[i][j] + total
print(M-len(set(total))+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
path = [[float("inf")]*N for i in range(N)]
ans = [[[float("inf")]]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
    ans[a-1][b-1] = [i]
    ans[b-1][a-1] = [i]
for i in range(N):
    path[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if path[i][k]+path[k][j] < path[i][j]:
                path[i][j] = path[i][k]+path[k][j]
                ans[i][j] = ans[i][k]+ans[k][j]
total = []
for i in range(N):
    for j in range(N):
        if ans[i][j] != [float("inf")]:
            total = ans[i][j] + total
print(M-len(set(total)))