---
# System prepended metadata

title: UVa 題目整理

---

# UVa 題目整理

## Floyd-Warshall (全源最短路徑)
### UVa 11463
``` cpp=1
#include "bits/stdc++.h"
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

int main() {
    int kase;
    cin >> kase;
    for (int r = 1; r <= kase; r++) {

        int n,fp,lp; cin >> n;
        vector<vector<int> > dist(n, vector<int>(n, inf));
        int path; cin >> path;
        while(path--){
            int tmp1,tmp2;
            cin>>tmp1>>tmp2;
            dist[tmp1][tmp2]=1;
            dist[tmp2][tmp1]=1;
        }
        cin>>fp>>lp;
        for(int i=0;i<n;i++)
            dist[i][i] = 0;

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) 
                        dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
                
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, dist[fp][i] + dist[i][lp]);
        cout << "Case "<<r<<": "<< ans << endl;
    }
    return 0;
}
```


## 水題
### UVa10041
```cpp=1
#include "bits/stdc++.h"
using namespace std;
main(){
	int kase;cin>>kase;
	while(kase--){
		int n;cin>>n;
		vector<int> vec(n);
		for(int &i:vec) cin>>i;
		sort(vec.begin(),vec.end());
		int mid = vec[vec.size()/2-1+vec.size()%2],sum=0;

		for(int i:vec)
			sum+= abs(mid-i);
		cout<<sum<<endl;
	}
}
```

### UVa11321
```cpp=1
#include "bits/stdc++.h"
using namespace std;
int m,n;
bool cmp(int a,int b){
	if(a%m!=b%m){
		return (a%m)<(b%m);
	}
	else{
		if((a%2)&&!(b%2))
			return 1;		
		if(!(a%2)&&(b%2))
			return 0;
		if((a%2)&&(b%2))
			return a>b;
		if(!(a%2)&&!(b%2))
			return a<b;	
	}
}
main(){
	while(cin>>n>>m){
		cout<<n<<' '<<m<<endl;
		if(!n||!m) break;
		vector<int> vec(n);
		for(int& i:vec)
			cin>>i;
		sort(vec.begin(),vec.end(),cmp);
		for(int i:vec)
			cout<<i<<endl;
	}
}
```


### UVa291

```cpp=1
#include <bits/stdc++.h>

using namespace std;

int ans[8];
bool m[6][6] = {0};

void S(int nowP, int n)
{
    ans[n] = nowP;
    if (n == 7)
    {
        for (int i = 0; i < 8; i++)
            cout << ans[i];
        cout << endl;
    }
    for (int i = 1; i < 6; i++)
    {
        if (m[nowP][i])
        {
            m[nowP][i] = m[i][nowP] = false;
            S(i, n + 1);
            m[nowP][i] = m[i][nowP] = true;
        }
    }
}

int main()
{
    m[1][2] = m[2][1] = true;
    m[1][5] = m[5][1] = true;
    m[1][3] = m[3][1] = true;
    m[2][3] = m[3][2] = true;
    m[2][5] = m[5][2] = true;
    m[3][4] = m[4][3] = true;
    m[3][5] = m[5][3] = true;
    m[4][5] = m[5][4] = true;
    S(1, 0);
}

```


### UVa568

```cpp=1
#include "bits/stdc++.h"

using namespace std;
long long ans=1;
int main(){
    int n; 
    while(cin>>n){
        for(int i=1;i<=n;i++){
            ans*=i;
            while(!(ans%10))
                ans/=10;
            ans%=5;
        }
        cout<<ans%10<<endl;
    }
}
```


### UVa579

```cpp=1
#include <bits/stdc++.h>

using namespace std;

int main(){
    float h,m;
    while(scanf("%f:%f",&h,&m)!=EOF&&(h||m)){
        float angle,ha,ma;
        ha=h*30.0+m/2;
        ma=m*6.0;
        angle=fabs(ha-ma);
        if(angle>180.0)
            angle=fabs(360.0-angle);
        printf("%.3f\n",angle);
    }
}
```