#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define INF 1000000 using namespace std; int gr[105][105]; int _mn(int a,int b) { if(a>b) return b; return a; } int _mx(int a,int b) { if(a>b) return a; return b; } int main() { bool f=0; int kase=1; int C,S,Q; int a,b,d; while(cin>>C) { cin>>S>>Q; if(C+S+Q==0) break; for(int
Category: Floyd warshall
280
This also can be solved using bfs or dfs. #include <iostream> #include <string.h> #include <vector> #define INF 1000000000 using namespace std; int gr[105][105]; int n,from,to; int tt; vector<int> vb; void init() { for(int i=0;i<105;i++) for(int j=0;j<105;j++) { gr[i][j]=INF; } } void floyd() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(gr[i][j]>gr[i][k]+gr[k][j]) gr[i][j] = gr[i][k]+gr[k][j];
10724
#include <iostream> #include <map> #include <cmath> #include <string> #include <vector> #include <cstring> #define INF 1000000000 #define EP 1e-6 using namespace std; struct point{ int x; int y; }; struct DD{ int i,j; double cst,edge; DD(double cst,double edge,int i,int j):cst(cst),edge(edge),i(i),j(j){ } bool operator < (const DD& d )const{ if(abs(cst-d.cst)>=EP) return cst<d.cst; if(abs(edge-d.edge)>=EP) return edge>d.edge; if(i!=d.i) return
247
#include <iostream> #include <map> #include <string> #include <cstring> #define INF 1000000000 using namespace std; int gr[30][30]; map<string,int> mp; map<int,string> np; int visit[30]; int main() { int n,m,c=0; int kase = 1; string s1,s2; while(cin>>n) { cin>>m; if(n+m==0) break; for(int i=0;i<26;i++) { for(int j=0;j<26;j++) { if(i==j) gr[i][j]=0; else { gr[i][j]=INF; } } } mp.clear(); np.clear(); int
10793
#include <iostream> #include <map> #include <vector> #define INF 1000000000 using namespace std; int L,D; int gr[105][105]; map<int,int> mp; int main() { int kase=1; int t,u,v,c; cin>>t; while(t–) { for(int i=0;i<105;i++) { for(int j=0;j<105;j++) { if(i==j) gr[i][j]=0; else gr[i][j]=INF; } } cin>>L>>D; for(int i=1;i<=D;i++) { cin>>u>>v>>c; if(gr[u][v]>c) { gr[u][v]=c; gr[v][u]=c; } } for(int k=1;k<=L;k++) { for(int
10075
Theory: Distance This uses the ‘haversine’ formula to calculate the great-circle distance between two points – that is, the shortest distance over the earth’s surface – giving an ‘as-the-crow-flies’ distance between the points (ignoring any hills they fly over, of course!). Haversine formula: a = sin²(Δφ/2) + cos φ1 * cos φ2 * sin²(Δλ/2) c = 2
10171
#include <iostream> #include <string.h> #include <vector> #include <fstream> #include <map> #define INF 1000000000 using namespace std; int grY[30][30]; int grO[30][30]; int main() { int N,KK,st,dst; char people,roadtyp,ct1,ct2; char start,dest; int energy; // ofstream out; // out.open("out.txt"); while(cin>>N) { if(N==0) break; for(int i=0;i<30;i++) { for(int j=0;j<30;j++) { if(i==j) { grY[i][j]=0; grO[i][j]=0; } else { grY[i][j]=INF; grO[i][j]=INF;
10269
This can be done two ways using floyed-warshall algorithm and also using bfs; Floyed warshall: #include <iostream> #include <queue> #include <cstring> #define INF 1500000 using namespace std; int gr[105][105]; int A,B,M,L,K; bool trace[105][15]; int d[105][15]; int shortestpath() { d[A+B][0]=0; queue<int> q; q.push(A+B); q.push(0); //trace[A+B][0]=1; while(!q.empty()) { int a = q.front();q.pop(); int boot = q.front();q.pop(); trace[a][boot]=0;
104
#include <iostream> #define FOR(i,n) for(int i=1;i<=n;i++) double gr[22][22][22]; int nxt[22][22][22]; int backtrck[22]; int n; using namespace std; int path(int step,int i,int j) { backtrck[step] = j; step-=1; while(step) { backtrck[step]=nxt[step][i][j]; step-=1; j= nxt[step][i][j]; } backtrck[step]=nxt[step+1][i][j]; return 0; } void init() { FOR(step,n) FOR(i,n) FOR(j,n) { nxt[1][i][j]=i; gr[step][i][j]=0; } } int main() { while(cin>>n) { init();
423
#include <iostream> #include <string.h> #define FOR(i,n) for(int i=1;i<=n;i++) #define INF 1<<29 using namespace std; int gr[101][101]; int main() { int n,MN; string a; while(cin>>n) { MN = INF; FOR(i,n) { FOR(j,n) { gr[i][j]=INF; if(i==j) gr[i][j]=0; } } for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { cin>>a; if(a=="x") gr[i][j]=gr[j][i]=INF; else { int t=0; for(int x=0;x<a.size();x++) { t =