結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー vjudge1
提出日時 2025-09-30 16:43:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,068 bytes
コンパイル時間 1,505 ms
コンパイル使用メモリ 170,732 KB
実行使用メモリ 69,328 KB
最終ジャッジ日時 2025-09-30 16:43:59
合計ジャッジ時間 8,124 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 36 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fir first
#define sec second
#define mkp make_pair 
#define pb push_back
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); ++ i )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); -- i )

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

namespace IO{
	const int SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;

template < class type > inline void chkmin ( type &x, type y ) { x = ( x <= y ? x : y ); }
template < class type > inline void chkmax ( type &x, type y ) { x = ( x >= y ? x : y ); }

const int N = 4005;

int id, n, m, ans = 8e18;
int dis[N][N], p[N];
bool vis[N];
priority_queue < pii, vector < pii >, greater < pii > > q;
vector < int > g[N];

void dijkstra ( int s ) {
  memset ( vis, 0, sizeof ( vis ) );
  memset ( p, 0x3f, sizeof ( p ) );
  p[s] = 0;
  q.push ( { p[s], s } );
  while ( !q.empty () ) {
    int x = q.top ().second;
    q.pop ();
    if ( vis[x] ) {
      continue;
    }
    vis[x] = 1;
    for ( int v : g[x] ) {
      if ( dis[x][v] && p[x] + dis[x][v] < p[v] ) {
        p[v] = p[x] + dis[x][v];
        q.push ( { -p[v], v } );
      }
    }
  }
}

void Solve () {
  ios :: sync_with_stdio ( false );
  cin.tie ( 0 ), cout.tie ( 0 );
  cin >> id >> n >> m;
  for ( int i = 1; i <= m; i ++ ) {
    int u, v, w;
    cin >> u >> v >> w;
    if ( !id ) {
      g[u].push_back ( v ), g[v].push_back ( u );
      dis[u][v] = dis[v][u] = w;
    }
    else {
      g[u].push_back ( v );
      dis[u][v] = w;
    }
  }
  for ( int i = 1; i <= n; i ++ ) {
    for ( int j = 1; j <= n; j ++ ) {
      if ( dis[i][j] ) {
        int tmpa = dis[i][j], tmpb = dis[j][i];
        dis[i][j] = dis[j][i] = 0;
        dijkstra ( j );
        ans = min ( ans, p[i] + tmpa );
        dis[i][j] = tmpa, dis[j][i] = tmpb;
      }
    }
  }
  cout << ( ans >= 8e18 ? -1 : ans );
}

signed main () {
#ifdef judge
  freopen ( "Code.in", "r", stdin );
  freopen ( "Code.out", "w", stdout );
  freopen ( "Code.err", "w", stderr );
#endif
  Solve ();
	return 0;
}
0