Submission #1070437

---

Source Code Expand

#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>


typedef long double ld;
typedef long long ll;
using namespace std;
const ll MX=5e6+9;
const ld pi = acos(-1);
const ll mod = 1e8;

//bool cmp ( int a,int b ) { return a>b; }

ll po ( ll a , ll b )
{
    if ( b==0 ) { return 1; }
    ll x = po ( a , b/2 );
    x *= x%mod;
    if ( b%2 ) { x*=a%mod; }
    return x%mod;
}

ll gcd (  ll a , ll b )
{
    if ( b==0 ) return a;
    else { gcd( b , a%b ); }
}
bool cmp ( int a , int b ) { return (a>b); }
int dx[]={ 0 , 0 , -1 , 1 , 1 , -1 , -1 , 1 };
int dy[]={ 1 , -1 , 0 , 0 , 1 , -1 , 1 , -1 };
ll a[MX],b[MX],c[MX];
int n,m,l;


ll bs ( ll x , ll id )
{
    ll st,en,mid;
    if ( id==2 )
    {
        st=0,en=m;
    }
    else { st=0,en=l; }
    ll ans=0;
    if ( id==2 ){
    ans=m-1;
    while ( st<=en )
    {
        mid = st+(en-st)/2;
        if ( b[mid]>=x ) { ans=mid; en=mid-1; }
        else { st=mid+1; }
    }
    }
    else
    {
    ans=l-1;
    while ( st<=en )
    {
        mid = st+(en-st)/2;
        if ( c[mid]>=x ) { ans=mid; en=mid-1; }
        else { st=mid+1; }
    }
    }
    return ans;
}

vector < pair<int,int> > v[MX];
ll p[104][104];
bool vis[105][105];
ll dis[105][105];
map < pair<int,int> ,bool> used;

int main()
{
    int n,m;
    cin>>n>>m;

    for ( int i=0 ; i<=n ; i++ )
        for ( int j=0 ; j<=n ; j++ )
        dis[i][j]=1e18;
    for ( int i=0 ; i<m ; i++ )
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back( make_pair( b , c ) );
        v[b].push_back( make_pair( a , c ) );
    }

    priority_queue < pair<int,int> > pq;

    for ( int i=1 ; i<=n ; i++ )
    {

        pq.push( make_pair( 0 , i ) );
        dis[i][i]=0;

        while ( !pq.empty() )
        {
            int node = pq.top().second;
            int cost = -pq.top().first;
            pq.pop();
            //cout<<i<<" "<<node<<endl;

            int sz = v[node].size();
            if ( vis[i][node] ) { continue; }
            vis[i][node]=1;
            for ( int j=0 ; j<sz; j++ )
            {
                int ncost = cost + v[node][j].second;
                int nxt = v[node][j].first;
                if ( dis[i][nxt]>ncost )
                {
                    p[i][nxt] = node;
                    dis[i][nxt] = ncost;
                    pq.push( make_pair( -ncost , nxt ) );
                }
            }
        }

    }
        int ans=m;

        for ( int i=1 ; i<=n ; i++ )
        {
            for ( int j=i+1 ; j<=n ; j++ )
            {
                int temp=j;
                while ( temp!=i )
                {
                    //cout<<temp<<" "<<p[i][temp]<<endl;
                    int n1,n2;
                    n1 = min( p[i][temp] , 1ll*temp );
                    n2 = max ( p[i][temp] , 1ll*temp );
                    temp = p[i][temp];
                    if ( used.find( make_pair( n1 , n2 ) )==used.end() )
                    {
                        ans--;
                        used[ make_pair( n1 , n2 ) ]=1;
                    }
                }
            }
        }

        cout<<ans;







	return 0;
}

Submission Info

Judge Result